AcWing 850. Dijkstra求最短路 II

原题链接：AcWing 850. Dijkstra求最短路 II

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

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

输入格式
第一行包含整数 n 和 m。

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

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

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

数据范围
1≤n,m≤1.5×10⁵,
图中涉及边长均不小于 0，且不超过 10000。
数据保证：如果最短路存在，则最短路的长度不超过 10⁹。

输入样例：

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

输出样例：

3
1

---

补充：图的邻接表存储

当图为稀疏图时，适合采用邻接表来存储

// 图的邻接表存储
// 类似于hash的拉链法
// 在每个结点上开一个单链表, 存储该点能到哪些点 用头插法

int h[N]; // h结点表 n个表头
int e[N];   // 存结点 弧的尾
int ne[N];  // 结点的next结点
int idx = 0;    // 下标

// 加入弧 就是在a的单链表中插入结点b
void add(int a, int b){
    e[idx] = b; // 建立一个结点b
    ne[idx] = h[a]; // 将b用头插法插入a的单链表 b->next = h[a]
    h[a] = idx++;   // 让h[a]指向b 这里的idx就是b的下标
}

// 初始化
memset(h, -1, sizeof h);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

方法一：Dijkstra算法（堆优化版）

思路：

此处n的最大能取150000，如果采用朴素版本的Dijkstra算法是肯定过不了的，因此需要优化

• 原版：找距离最近的点t需要O(n²)；用t来更新其他点的距离（其实是更新边）需要O(m)，总体的时间复杂度是O(n²)
• 堆优化版：找距离最近的点t需要O(n)；在堆中修改一个数需要O(logn)，修改m次总共需要O(mlogn), m和n是一个级别，总体的时间复杂度就是O(nlogn)

不采用手写堆，直接用优先队列来实现，优先队列不支持修改，因此实现方式就是 冗余 ，每次需要修改的时候就往堆中插入一条边，空间复杂度为O(m)

由于有冗余，当前找到的最小边可能是已经确定最短路的结点，用st[ ]进行判断，如果已经确定，直接跳过就可以了

C++ 代码：

#include 
#include 
#include 
#include 
using namespace std;

typedef pair<int, int> PII;
const int N = 1e6 + 10;

int n, m;
int h[N], w[N], e[N], ne[N], idx;   // 稀疏图 用邻接表
int dist[N];
bool st[N];

// 邻接表加边
void add(int a, int b, int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++ ;
}

// 堆优化版 dijkstra
int dijkstra(){
    
    // 初始化
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    // 优先队列 存<到源点的最短距离,结点编号> 会有冗余数据
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});

    while (heap.size()){
        // 距离最近的点
        auto t = heap.top();
        heap.pop();

        // ver结点编号 distance到源点的最短距离
        int ver = t.second, distance = t.first;

        // 如果是冗余数据 就跳过
        if (st[ver]) continue;
        
        // 标记ver已确定最短路
        st[ver] = true;

        // 用ver来更新所有点的距离
        for (int i = h[ver]; i != -1; i = ne[i]){
            int j = e[i];
            
            if (dist[j] > dist[ver] + w[i]){
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    
    cout << dijkstra() << endl;

    return 0;
}
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

复杂度分析：

• 空间复杂度：O(m)，优先队列会存冗余，会存下所有的边
• 时间复杂度：O(nlogn)