P4779 【模板】单源最短路径（标准版）

题目背景

2018 年 7 月 19 日，某位同学在 NOI Day 1 T1 归程 一题里非常熟练地使用了一个广为人知的算法求最短路。

然后呢？

$100 \rightarrow 60$；

$\text{Ag} \rightarrow \text{Cu}$；

最终，他因此没能与理想的大学达成契约。

小 F 衷心祝愿大家不再重蹈覆辙。

题目描述

给定一个 $n$ 个点，$m$ 条有向边的带非负权图，请你计算从 $s$ 出发，到每个点的距离。

数据保证你能从 $s$ 出发到任意点。

输入格式

第一行为三个正整数 $n, m, s$。
第二行起 $m$ 行，每行三个非负整数 $u_i, v_i, w_i$，表示从 $u_i$ 到 $v_i$ 有一条权值为 $w_i$ 的有向边。

输出格式

输出一行 $n$ 个空格分隔的非负整数，表示 $s$ 到每个点的距离。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

输出 #1

1
0 2 4 3

说明/提示

样例解释请参考 数据随机的模板题。

$1 \leq n \leq 10^5$；

$1 \leq m \leq 2\times 10^5$；

$s = 1$；

$1 \leq u_i, v_i\leq n$；

$0 \leq w_i \leq 10 ^ 9$,

$0 \leq \sum w_i \leq 10 ^ 9$。

本题数据可能会持续更新，但不会重测，望周知。

dijkstra算法详解

什么是dijkstra？

  • dijkstra是一种单源最短路径算法,时间复杂度上限为O(n^2)(朴素),在实际应用中较为稳定;加上堆优化之后更是具有O((n+m)logn)的时间复杂度,在稠密图中有不俗的表现.(适用于不含负权边的图)

dijkstra流程

  1. 把点分为已经确定最短路的黑点和未确定最短路的白点
  2. 用dis数组表示该点距起点的距离
  3. 初始化：dis[start] = 0，其余全标成INF
  4. 找出所有白点中dis最小的点v，将它标成黑点
  5. 用v来更新所有它邻接点u的dis，dis[u] = min(dis[u], dis[v] + len(v->u))
  6. 再重复4, 5直到所有点都被标成黑点

dijkstra的解释

  • 到达一个白点s的可能情况分为以下两种：
    1. 从黑点到达
    2. 先到其他白点，再到达它
  • 而当s的dis已经成为所有白点中最小时，它的dis不再可能被第二种情况更新(在所有权值非负的情况下)，因为先到任何一个其他白点的代价都比直接到它更大
  • 而这时留在场上的白点全都是可能被s更新的点，所以再用它来更新一遍dis
  • 我们可以发现dijkstra的本质思想就是==贪心==，它只适用于不含负权边的图

dijkstra的堆优化

  • 观察dijkstra的流程，易知查找最小dis的步骤可使用priority_queue优化
  • 我们可以用堆对dis数组进行维护,用O(log​n)的时间取出堆顶元素并删除,用O(log​n)遍历每条边,总复杂度O((n+m)logn)

代码示例与注解

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
#include <bits/stdc++.h>
using namespace std;
const int MaxN = 1e5 + 10, MaxM = 5e5+10;
struct edge // 边
{
    int to, dis, next;
};

edge e[MaxM];
int head[MaxN], dis[MaxN], cnt;
bool vis[MaxN]; // 记录该点的最短路有没有确定
int n, m, s; // s是出发点

inline void add_edge(int u, int v, int d)  { // 构建邻接表
    cnt++; // 该边的编号
    e[cnt].dis = d; // 该边的权重
    e[cnt].to = v; // 该边的终点
    e[cnt].next = head[u]; // e[cnt]的下一条边是原先点u接上的第一条边
    head[u] = cnt; // 更新点u对应的边的编号
}

struct node // 点
{
    int dis; // 距出发点的距离
    int pos; // 点的编号
    bool operator <(const node &x) const {
        return x.dis < dis;
    }
};
priority_queue<node> q;

inline void dijkstra() {
    dis[s] = 0;
    q.push((node){0, s});
    while (!q.empty()) {
        node tmp = q.top(); // 取出堆顶(dis最小)
        q.pop();
        if (vis[tmp.pos]) continue; // 之前已确定过最短路
        int v = tmp.pos;
        vis[v] = 1;
        // 更新点tmp.pos所连接的所有未vis点的dis
        // l = head[tmp.pos]是它所连的第一条线的编号 e[l].next是下一条
        // 以此类推遍历所有邻接边 
        for(int l = head[v]; l != 0; l = e[l].next) {
            if(vis[e[l].to]) continue;             
            int next_dot = e[l].to;
            if(dis[next_dot] > e[l].dis + dis[v]) {
                dis[next_dot] = e[l].dis + dis[v];
                q.push((node){dis[next_dot], next_dot});
            }
        }
    }
}

int main() {
    scanf("%d%d%d", &n, &m, &s);
    memset(dis, 0x3f, sizeof dis);
    int u, v, d;
    for(int i=0; i<m; i++) {
        scanf("%d%d%d", &u, &v, &d);
        add_edge(u, v, d);
    }
    dijkstra();
    for(int i=1; i<=n; i++) {
        printf("%d ", dis[i]);
    }
    printf("\n");
    return 0;
}

补充说明

  • 为便于寻找邻接点的操作 本例使用邻接表储存图