[AcWing.849. Dijkstra求最短路 I]

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 -1。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式

输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 -1。

数据范围

1 < n < 500,
1 < m < 10^5,
图中涉及边长均不超过10000。

输入样例：

1
2
3
4
3 3
1 2 2
2 3 1
1 3 4

输出样例：

1
3

算法思想

朴素Dijkstra可以用来求有向图的单源最短路(一个点到其余点的最短距离，一般默认是求起点1到其余点的距离)，无向图可以看作特殊的有向图，只需要建图的时候建两条边即可。

邻接矩阵版，主要变量名解释:

1
2
3
4
5
6
7
8
9
10
11
// 最大点、边的数组容量、正无穷
const int N = 510, M = 100010, INF = 0x3f3f3f3f;

// 点、边
int n, m;
// 使用邻接矩阵表示图
int g[N][N];
// 源点距离其它点的距离
int dist[N];
// 该点是否已经属于最短路集合中
bool st[N];

易错点：

  1. main函数一开始
    1
    2
    // 很重要的一点！一开始就将邻接矩阵的距离都初始化为无穷大
    memset(g, 0x3f, sizeof g);
  2. dijkstra函数内一开始
    1
    2
    // 初始化源点距离数组为无穷大
    memset(dist, 0x3f, sizeof dist);
  3. dijkstra逻辑细节别都嵌套到for循环里面去了
    1
    2
    3
    4
    5
    6
    7
    8
    9
    // 枚举所有点（这层循环要求点的编号也能对应上，从1开始）
    for(int j = 1; j <= n; j++){
        // 如果这个点还没有被纳入最短路集合里面
        // t是-1，或者 有点j存在使得 有更短的路径
        // 更新 t
        if(!st[j] && (t == -1 || dist[j] < dist[t])){
            t = j;
        }
    }
    1
    2
    3
    4
    5
    6
    7
    // 确定这个t点是最短路集合里面的点
    st[t] = true;
    // 由于t这个点加入，需要更新一下距离
    for(int j = 1; j <= n; j++){
        // g[t][j]是边权
        dist[j] = min(dist[j], dist[t] + g[t][j]);
    }

代码实现

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
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

// 最大点、边的数组容量、正无穷
const int N = 510, M = 100010, INF = 0x3f3f3f3f;

// 点、边
int n, m;
// 使用邻接矩阵表示图
int g[N][N];
// 源点距离其它点的距离
int dist[N];
// 该点是否已经属于最短路集合中
bool st[N];

int dijkstra(){
    // 初始化源点距离数组为无穷大
    memset(dist, 0x3f, sizeof dist);
    
    // 源点距离源点它自己的距离为0，源点默认为1
    dist[1] = 0;
    
    // 枚举所有点（n次），虽然dist[1] = 0，但实际上它还没加入最短路集合中。
    for(int i = 0; i < n; i++){
        // 保存当前循环，距离最短的点
        int t = -1;
        
        // 枚举所有点（这层循环要求点的编号也能对应上，从1开始）
        for(int j = 1; j <= n; j++){
            // 如果这个点还没有被纳入最短路集合里面
            // t是-1，或者 有点j存在使得 有更短的路径
            // 更新 t
            if(!st[j] && (t == -1 || dist[j] < dist[t])){
                t = j;
            }
        }
        
        // 确定这个t点是最短路集合里面的点
        st[t] = true;
        // 由于t这个点加入，需要更新一下距离
        for(int j = 1; j <= n; j++){
            // g[t][j]是边权
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        }
    }
    // 从源点到终点的距离
    return dist[n];
}

int main(){
    
    cin >> n >> m;
    // 很重要的一点！一开始就将邻接矩阵的距离都初始化为无穷大
    memset(g, 0x3f, sizeof g);
    
    // 建图
    while(m --){
        int a, b, c;
        cin >> a >> b >> c;
        // 保证没有重边，如果有重边，保留一个最小的边就行
        g[a][b] = min(g[a][b], c);
    }
    
    // 求最短路
    int res = dijkstra();
    
    // 如果结果是正无穷，输出-1，否则输出结果
    if(res == INF) puts("-1");
    else cout << res << endl;
    
    return 0;
}