图论除了最小生成树，Kruskal以外，Dijkstra算法也是重点的模块，Dijkstra算法变种题很多，经典的我也是收藏一下，以后方便寻找，hah
题目描述（废话，建议不看）
“呼！！终于到了，可是接下来要怎么走才能到达楚楚街港港呢？”亮亮在醋溜港直发愁。 突然“啾”的一下，一只银色小船出现在亮亮的面前， 上面坐着小精灵丹丹“又见面了，有什么可以帮助你的么？”小精灵向亮亮眨了眨眼睛，微笑着说。 “我想去楚楚街港，但我不知道要怎么走， 请问你可以告诉我么？”亮亮按捺着激动的 心 情轻声问道。 “楚楚街港呀......那是个特别美好的地方”小精灵歪着头想了想，说“我只能告诉 你大海上所有的航线， 剩下的就只能靠你自己啦~” “只有所有的航 线呀”，亮亮的内心再三挣扎，却又没有其他的办法。 “不管有多困难，我一定要达到楚楚街港，请你告诉我吧”亮亮坚定地对小精灵说。 小精灵欣赏地点了点头，递给亮亮一张航线图，并叮嘱道“时限是1000天，一定要到哦~”，然后如来时一般“啾”的一声，消失了。 亮亮现在 迫切地想要抵达楚楚街 港，请问亮亮最快能在第几天抵达楚楚街港呢？输入描述:
一行包含两个整数N(2<=N<=500),M(1<=M<=2000)，用单个空格隔开。表示公有N个港，M条航线。起点为1，终点为N。 接下来M行，每行包含五个整数P,Q(1<=P,Q<=n), K(1<=K<=1000), X,Y(0<=X,Y<=10000),代表P,Q两个港有航线并需要K天， 并且该航线在第X天到第Y天天气恶劣 不可通行。输出描述:
一个整数，即亮亮最快能在第几天抵达楚楚街港输入
4 4 2 1 1 7 13 4 3 2 10 11 1 3 8 9 12 2 3 3 2 10输出
14如果还不是很理解dijkstra算法的同学建议先点击：dijkstra算法模板详细介绍
这里的taken数组其实就是一个标记是否访问过，是否能作为下一次更新最短路径的bool型的st[]数组
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <climits> #include <vector> using namespace std; const int maxn = 500 + 5; int dp[maxn], taken[maxn], n, m; struct Node{ int x, y, val, start, end; Node(int a, int b, int c, int d, int e){ x = a; y = b; val = c; start = d; end = e; } }; vector<Node> v[maxn]; //每一个起始点 对应的结构体， 作为拓扑图，这里是结构体Node作为拓扑图 int main(){ while(scanf("%d%d", &n, &m) != EOF){ memset(dp, 0x3f, sizeof(dp)); //初始化dp数组为0x3f，dp数组就是距离数组 memset(taken, 0, sizeof(taken)); for(int i = 0; i < m; i++){ int a, b, c, d, e; scanf("%d%d%d%d%d", &a, &b, &c, &d, &e); Node n1(a, b, c, d, e); Node n2(b, a, c, d, e); //这里jijkstra()算法算的是结构体 v[a].push_back(n1); // v[a].push_back(n1); 从a出发到达的所有点的各种信息 v[b].push_back(n2); // 双向边，反向建图 } dp[1] = 0; //第一个点先经历 所以节点为1 for(int k = 0; k < n; k++){ int min_dp = -1; // min_dp是最小值，最小加进来的 for(int i = 1; i <= n; i++) if(!taken[i] && (min_dp == -1 || dp[i] < dp[min_dp])) min_dp = i; taken[min_dp] = 1; //选择个最短的点 标记为已经加入最短距离的数组中，接下来用来哦更新其它点 for(int i = 0; i < v[min_dp].size(); i++){ Node n = v[min_dp][i]; //这一个点，也就是轩主最小距离min_dp的下一个点 if(dp[n.x]>=n.end || (dp[n.x]+n.val)<n.start)//暴风雨来临前已经溜了或者暴风雨刮完了才到 dp[n.y] = min(dp[n.y], dp[n.x] + n.val); else dp[n.y] = min(dp[n.y], n.end + n.val);//要等暴风雨结束才能走 } } cout<< dp[n] + 1<< endl;//天数是从第一天开始算的 没有第0天 所以加一 } return 0; }做个标记。挺经典的，图论之重点算法
