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 1010 3 5 111 4 5 312 4 6 513 5 6 914 615 */16 #include <iostream>17 #include <vector>18 #include <algorithm>19 #include <cstdio>20 using namespace std;21 22 const int maxn = 1010 + 20;23 const int INF = 99999999;24 int cost[maxn][maxn];      //表示边e=(u,v)的权值 (不存在这条边时设为INF)25 int d[maxn];               //顶点出发的最短距离26 bool used[maxn];           //已经使用过的图27 int V, E;28 void init();29 void dijkstra(int s);30 void input();31 32 void init()33 {34     for (int i = 0; i < V; i++) {35         for (int j = 0; j < V; j++) {36             if (i == j) {37                 cost[i][j] = 0;38             }39             else {40                 cost[i][j] = INF;41             }42         }43     }44 }45 46 void dijkstra(int s)47 {48     fill(d, d + V, INF);49     fill(used, used + V, false);50     d[s] = 0;51 52     while (true) {53         int v = -1;54         //从尚未使用过的顶点中选择一个距离最小的顶点55         for (int u = 0; u < V; u++) {56             if (!used[u] && (v == -1 || d[u] < d[v])) {57                 v = u;58             }59         }60         if (v == -1) break;        //已经没有尚未使用的点了61         used[v] = true;            //标志v已访问62 63         for (int u = 0; u < V; u++) {64             d[u] = min(d[u], d[v] + cost[u][v]);65         }66     }67 }68 69 void input()70 {71     int s, t, ct;72     for (int i = 0; i < E; i++)73     {74         cin >> s >> t >> ct;75         cost[s][t] = cost[t][s] = ct;76     }77 }78 79 int main()80 {81     cin >> V >> E;           //输入顶点数和边数82     init();                  //必须要初始化83     input();                 //输入临接的边和权值84     dijkstra(0);             //设置起点85     int ov;86     cin >> ov;               //输入终点87     cout << d[ov] << endl;88     return 0;89 }

 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 1010 3 5 111 4 5 312 4 6 513 5 6 914 615 */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 = 99999999;27 struct edge28 {29     int to, cost;30 };31 typedef pair<int, int> P;      //first是最短距离，second是顶点的编号32 int V, E;33 vector<edge> G[maxn];34 int d[maxn];35 //void init();36 void input();37 38 void dijkstra(int s)39 {40     //通过指定greater<P>参数,堆按照first从小到大的顺序取出值41     priority_queue<P, vector<P>, greater<P> > que;42     fill(d, d + V, INF);43     d[s] = 0;44     que.push(P(0, s));45 46     while (!que.empty()) {47         P p = que.top(); que.pop();48         int v = p.second;49         if (d[v] < p.first) continue;50         for (int i = 0; i < G[v].size(); i++) {51             edge e = G[v][i];52             if (d[e.to] > d[v] + e.cost) {53                 d[e.to] = d[v] + e.cost;54                 que.push(P(d[e.to], e.to));55             }56         }57     }58 }59 60 //void init()61 //{    62 //}63 64 void input()65 {66     int s, t, ct;67     edge tmp;68     for (int i = 0; i < E; i++) {69         cin >> s >> t >> ct;70         tmp.to = t; tmp.cost = ct;71         G[s].push_back(tmp);72         //无向图，反向也需要连接73         tmp.to = s; tmp.cost = ct;74         G[t].push_back(tmp);75     }76 }77 78 int main()79 {80     cin >> V >> E;81     //init();82     input();83     dijkstra(0);84     int ov;85     cin >> ov;86     cout << d[ov] << endl;87     return 0;88 }