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 6
15 */
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 }
//解法二:
需要优化的是数值的插入（更新）和取出最小值两个操作，因此使用堆就可以了。把每个顶点当前的最短距离用堆维护，在更新最短距离时，把对应的元素往根的方向移动以满足堆的性质。而每次从堆中取出的最小值就是下一次要使用的顶点。这样堆中元素共有O(|V|)个。更新和取出数值的操作有O(|E|)次，因此整个算法复杂度是O(|E|log|V|)。
下面是使用STL的priority_queue的实现。在每次更新时往堆里插入当前最短距离和顶点的值对。插入的次数是O(|E|)次，因此元素也是O(|E|)个。当取的最小值不是最短距离的话，就丢弃这个值。
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 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 = 99999999;
27 struct edge
28 {
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 }