首页 程序设计 图论 最短路算法

# 基础 Dijkstra 算法

# 题目背景

给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

# 输入格式

第一行包含三个整数 n,m,sn,m,s，分别表示点的个数、有向边的个数、出发点的编号。
接下来 mm 行每行包含三个整数 u,v,wu,v,w，表示一条 u→vu \to v 的，长度为 ww 的边。

# 输出格式

输出一行 nn 个整数，第 ii 个表示 ss 到第 ii 个点的最短路径，若不能到达则输出 231−12^{31}-1。

# 数据范围

对于 100%100\% 的数据：1≤n≤5001 \le n \le 500，1≤m≤1051\le m \le 10^5，1≤u,v≤n1\le u,v\le n，w≥0w\ge 0，∑w<10000\sum w < 10000，保证数据随机。

# 算法思路

不能有负权边！！
不断选出途中没被确定最短路径的点，并用此点更新它邻接表上的点，直到无法取出点的时候，跳出循环。

c++
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
const int N = 510, M = 1e5 + 10;
int h[N], e[M], ne[M], w[M], idx = 0;
bool st[N];
int n, m, a, b, c, d[N];

int add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

signed main () {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    memset(h, -1, sizeof h);
    memset(d, 0x3f, sizeof d);

    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> a >> b >> c, add(a, b, c);

    d[1] = 0;

    while (true) {
        int t = -1;

        for (int i = 1; i <= n; i++)
            if (!st[i] && (t == -1 || d[i] < d[t]))
                t = i;
        
        if (t == -1)
            break;

        st[t] = 1;
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            d[j] = min(d[j], d[t] + w[i]);
        }
    }

    cout << (d[n] == 0x3f3f3f3f ? -1 : d[n]) << endl;
}

# 边权 + 点权 + 输出路径的 Dijkstra

# 题目背景

作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。

# 输入格式

输入第一行给出 44 个正整数 N、M、S、DN、M、S、D，其中 N（2≤N≤500）N（2≤N≤500）是城市的个数，顺便假设城市的编号为 0→(N−1)0 \to (N−1)；MM 是快速道路的条数；SS 是出发地的城市编号；DD 是目的地的城市编号。
第二行给出 NN 个正整数，其中第 ii 个数是第 ii 个城市的救援队的数目，数字间以空格分隔。随后的 M 行中，每行给出一条快速道路的信息，分别是：城市 11、城市 22、快速道路的长度，中间用空格分开，数字均为整数且不超过 500500。输入保证救援可行且最优解唯一。

# 输出格式

第一行输出最短路径的条数和能够召集的最多的救援队数量。第二行输出从 SS 到 DD 的路径中经过的城市编号。数字间以空格分隔，输出结尾不能有多余空格。

# 算法思路

c++
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
int side[N][N]; // 记录边权
int dis[N]; // 记录最短路长度
int aid[N]; // 记录每个城市救援队人数
int val[N]; // 记录一个点，在起点到他的最短路径上，能召集到的最多的救援队人数
int cnt[N]; // 记录抵达一个点的最短路径条数
int path[N]; // 记录每个人的父结点（输出路径用）
int n, m, s, d;
bool st[N];

// 输出路径
void output(int x) {
    if (path[x] == -1)
        return;
    output(path[x]), cout << " " << x;
}

void solve () {
    memset(dis, 0x3f, sizeof dis), memset(side, 0x3f, sizeof side);
    
    cin >> n >> m >> s >> d;
    for (int i = 0; i < n; i++)
        cin >> aid[i], cnt[i] = 1;

    for (int i = 1, x, y, z; i <= m; i++)
        cin >> x >> y >> z, side[x][y] = side[y][x] = z;

    // 起始点最短路径长度 = 0, 能召集的救援队人数 = 自己所在地的救援队人数, 没有父节点 = -1
    dis[s] = 0, val[s] = aid[s], path[s] = -1;

    while (true) {
        int t = -1;
        for (int i = 0; i < n; i++)
            if (!st[i] && (t == -1 || dis[i] < dis[t]))
                t = i;

        if (t == -1)
            break;

        st[t] = 1;

        for (int i = 0; i < n; i++) {
            // 如果有更短路径
            if (!st[i] && dis[i] > dis[t] + side[t][i])
                // 更新路径长, 更新能摇来的救援队人数, 更新父节点, 路径数 = 上一点的路径数
                dis[i] = dis[t] + side[t][i], val[i] = val[t] + aid[i], path[i] = t, cnt[i] = cnt[t];
            // 如果出现同长度路径
            else if (!st[i] && dis[i] == dis[t] + side[t][i]) {
                // 路径数 = 本身能走到的路径数(cnt[i]) + 发现的新点能走到的路径数(cnt[t])
                cnt[i] += cnt[t];
                // 如果能摇来的救援队人数更多则更新
                if (val[t] + aid[i] > val[i])
                    path[i] = t, val[i] = val[t] + aid[i];
            }
        }
    }

    cout << cnt[d] << " " << val[d] << endl;
    cout << s, output(d);
}