1 #define _CRT_SECURE_NO_WARNINGS 2 /* 3 7 10 4 0 1 5 5 0 2 2 6 1 2 4 7 1 3 2 8 2 3 6 9 2 4 10 10 3 5 1 11 4 5 3 12 4 6 5 13 5 6 9 14 0 6 15 */ 16 #include <iostream> 17 #include <vector> 18 #include <utility> 19 #include <queue> 20 #include <functional> 21 #include <algorithm> 22 #include <cstdio> 23 using namespace std; 24 25 const int maxn = 1010 + 20; 26 const int INF = 9999999; 27 int V, E; 28 int Prev[maxn]; //最短路上的前驱顶点 29 int d[maxn]; 30 int cost[maxn][maxn]; //i->j 上的权值 31 int used[maxn]; 32 33 void input(); 34 void init(); 35 //求从起点s出发到各个顶点的最短距离 36 void dijkstra(int s); 37 38 void init() { 39 for (int i = 0; i < V; i++) { 40 for (int j = 0; j < V; j++) { 41 if (i == j) { 42 cost[i][j] = 0; 43 } 44 else { 45 cost[i][j] = INF; 46 } 47 } 48 } 49 } 50 51 void input() 52 { 53 int s, t, ct; 54 for (int i = 0; i < E; i++) { 55 cin >> s >> t >> ct; 56 cost[s][t] = cost[t][s] = ct; 57 } 58 } 59 60 //从s点出发到各个顶点的最短距离 61 void dijkstra(int s) 62 { 63 fill(d, d + V, INF); 64 fill(used, used + V, false); 65 fill(Prev, Prev + V, -1); 66 d[s] = 0; 67 68 while (true) { 69 int v = -1; 70 for (int u = 0; u < V; u++) { 71 if (!used[u] && (v == -1 || d[u] < d[v])) 72 v = u; //找出到下一条尝试的顶点中距离最短的点 73 } 74 75 if (v == -1) break; 76 used[v] = true; 77 78 for (int u = 0; u < V; u++) { 79 if (d[u] > d[v] + cost[v][u]) { 80 d[u] = d[v] + cost[v][u]; //从v到各个临边u中最短的路-->存放到d[u]，用于下一次计算 81 Prev[u] = v; //u的前驱是v 82 } 83 } 84 } 85 } 86 87 //到顶点t的最短路 88 vector<int> get_path(int t) { 89 vector<int> path; 90 for (; t != -1; t = Prev[t]) path.push_back(t); //不断沿着Prev[t]走直到 t = s 91 //这样得到的是按照t到s的顺序，所以翻转之 92 reverse(path.begin(), path.end()); 93 return path; 94 } 95 96 97 int main() 98 { 99 cin >> V >> E; 100 init(); 101 input(); 102 int st, ov; 103 cin >> st >> ov; 104 dijkstra(st); 105 cout << d[ov] << endl; 106 cout << "Debug..........\n"; 107 vector<int> path = get_path(ov); 108 for (int i = 0; i < path.size(); i++) { 109 cout << path[i] << " "; 110 } 111 112 cout << endl; 113 return 0; 114 }
