cht很热爱学习，他打算偷偷跑回学校学习，为了多学习他希望可以找最快的路线回到学校。 北京市里有N个(2 <= N <= 1000)个地铁站，编号分别为1…N。cht家在1号地铁站旁边，清华大学旁边是N号地铁站。地铁站之间共有M (1 <= M <= 2000)条双向路径。 cht现在在1号地铁站，他希望知道到学校最短要多长时间。可以保证cht能到达学校。忽略cht在换乘地铁时需要的等待时间
第一行:两个整数:M和N 接下来M行:每一行有A B C三个整数。代表A站到B站或者B站到A站需要C分钟，C的范围为1到100。
一个整数，表示cht回到学校的最少时间。
5 5 1 2 20 2 3 30 3 4 20 4 5 20 1 5 100
90
Dijkstra算法的朴素实现：
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <string> #include <cstring> #include <map> #include <queue> using namespace std; typedef long long LL; const int N = 1005; int n, m, g[N][N], dist[N], st[N]; //g数组是记录从某点到某点的权值，dist数组表示任意点到点1的最短距离，st数组是标记已求出最短路径的顶点 int read(){ int x, f = 1; char ch; while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1; x = ch - '0'; while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48; return x * f; } int dijkstra(){ int i, j, t; memset(dist, 0x3f, sizeof(dist)); //把所有点到起点最短距离初始化为正无穷 dist[1] = 0; //起点到起点的最短距离为0 for(i = 1; i <= n; i++){ //每轮循环得到一个确定最短路径的顶点 t = -1; //t是个临时变量，为了确定某个点到起点的最短距离，并且把其放入已求出最短路径的顶点的集合里面 for(j = 1; j <= n; j++){ if(!st[j] && (t == -1 || dist[t] > dist[j])) t = j; } st[t] = 1; //标记t点已经被放入已求出最短路径的顶点的集合里面 for(j = 1; j <= n; j++){ dist[j] = min(dist[j], dist[t] + g[t][j]); //更新未确定最短路径的顶点 目前已得到的最短路径 } } if(dist[n] == 0x3f3f3f3f) return -1; //此点跟起点不是连通的 return dist[n]; //返回点n到起点的最短路径 } int main(){ int a, b, c; m = read(); n = read(); memset(g, 0x3f, sizeof(g)); //把各个点之间的距离都初始化为正无穷 while(m--){ a = read(); b = read(); c = read(); g[a][b] = g[b][a] = min(g[a][b], c); //因为这是无向图，所以从a到b和从b到a的距离相同，两点的距离可能会被读入不同的数据，取那个最短的距离，便于后续求最短路径 } printf("%d\n", dijkstra()); return 0; }Dijkstra算法利用优先队列实现：
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <string> #include <cstring> #include <map> #include <queue> using namespace std; typedef long long LL; int read(){ int x, f = 1; char ch; while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1; x = ch - '0'; while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48; return x * f; } typedef pair<int, int> PII; const int N = 4005; int n, m, h[N], w[N], e[N], ne[N], idx, dist[N], st[N]; void add(int a, int b, int c){ e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx++; } int dijkstra(){ int ver, distance, i, j; memset(dist, 0x3f, sizeof(dist)); dist[1] = 0; priority_queue <PII, vector<PII>, greater<PII> > heap; heap.push({0, 1}); while(heap.size()){ PII t = heap.top(); heap.pop(); ver = t.second; if(st[ver]) continue; st[ver] = 1; for(i = h[ver]; i != -1; i = ne[i]){ j = e[i]; if(dist[j] > dist[ver] + w[i]){ dist[j] = dist[ver] + w[i]; heap.push({dist[j], j}); } } } if(dist[n] == 0x3f3f3f3f) return -1; return dist[n]; } int main(){ int a, b, c; m = read(); n = read(); memset(h, -1, sizeof(h)); while(m--){ a = read(); b = read(); c = read(); add(a, b, c); add(b, a, c); } printf("%d\n", dijkstra()); return 0; }