本题目要求通过读入无向网的边的信息（省略了各顶点的信息，仅用顶点编号来表示），构造图，并利用Dijkstra算法，求出指定源点到其它各点的最短路径。

输入样例:

第一行，两个整数，顶点数vN和边数eN。 以后若干行，是相关边的信息，无向图的边是对称的，只输入一半的边（小编号到大编号的，间以空格），最后两行各一个整数，前一个指定源点，后一个指定的查询的终到点。 （注意，示例中34条边，只输入了17条边的信息）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
10 34
0 1 2
0 3 5
1 2 5
1 3 2
2 4 8
2 5 4
3 5 4
3 6 2
4 7 5
4 5 2
5 6 3
5 7 9
5 8 7
6 8 7
7 8 3
7 9 4
8 9 8
0
8

输出样例:

在一行中输出从源点到指定终点的短路径及代价，注意：所有符号均为西文符号。

1
0-->1-->3-->6-->8:13

思路：

  • 单源最短路径算法，注意源点和终点相同的情况，需要特判输出

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <vector>
using namespace std;

typedef struct {
    int v, w;
} Node;

const int inf = 65535;
int n, e, s, d;
int dis[1001], pre[1001];
vector<Node> v[1001];
bool vis[1001] = {false};

void dijkstra(int s) {
    fill(dis, dis + 1001, inf);
    dis[s] = 0;
    for (int i = 0; i < n; i++) {
        int u = -1, minx = inf;
        for (int j = 0; j < n; j++) {
            if (!vis[j] && dis[j] < minx) {
                u = j;
                minx = dis[j];
            }
        }
        if (u == -1)
            break;
        vis[u] = true;
        for (int j = 0; j < v[u].size(); j++) {
            int x = v[u][j].v;
            if (!vis[x] && dis[u] + v[u][j].w < dis[x]) {
                dis[x] = dis[u] + v[u][j].w;
                pre[x] = u;
            }
        }
    }
}

int main() {
    scanf("%d %d", &n, &e);
    for (int i = 0; i < e / 2; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        v[a].push_back(Node{b, c});
        v[b].push_back(Node{a, c});
    }
    scanf("%d %d", &s, &d);
    if (s == d) {
        printf("%d-->%d:0", s,s);
        return 0;
    }
    dijkstra(s);
    vector<int> ve;
    int x = d;
    while (x != s) {
        ve.push_back(x);
        x = pre[x];
    }
    printf("%d", s);
    for (int i = ve.size() - 1; i >= 0; i--)
        printf("-->%d", ve[i]);
    printf(":%d", dis[d]);
    return 0;
}