【每日一题】 Dijkstra求最短路 II，堆优化算法

题目描述

---

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×105,
图中涉及边长均不小于 0，且不超过 10000。
数据保证：如果最短路存在，则最短路的长度不超过 109。

题解

---

边少节点多的场景比较适合，例如边和节点的比例接近，1：1。并且需要借助邻接表存储的形式才能使用。时间复杂度O(MlogN)
需要看看这篇->数组模拟单链表
需要注意int h[N], e[M], ne[M], w[M], idx;实际上才是正确的定义方式h是头节点是数量，题目通常用N表示节点的数量，M表示边的数量。所以实际上我们是需要定义N个头节点，M个边的对端，M个next节点（因为一个边都连接着下一条边，即使是桶的尾节点，也需要用-1作为标识），w表示权值（一条边一个），idx定位当前尚未被使用的一个数组。

可以理解为下标标识为一个节点，通过ne[下标]可以拿到他的next，e[下标]拿到他的对边，w[下标]拿到该节点（x- > y）的权值。（注意，由于只有在初始化的时候才会更新w，所以它的起始边是由初始化决定的。也可以理解是下标所对应的桶就是起始点。）h[下标]可以获取对应节点所在的头节点。

• 并且需要注意pair 当中第一个元素存储的是权值，第二个元素存储的是对边。这是因为pair的比较方式是从左往右进行比较，而我们只需要确保按照权值进行比较即可。
• 需要注意，每一个桶只会遍历一次，即使有重边，那么最小的边也会在最上面，且后续st数组会记录这个点，后续也不会更新这个节点了。自环实际上也会在w[src] + distance < dist[dst]解决，因为这样子实际上只要这个点不是负数，那么更新的时候就不会被记录。
• 优先级队列存放的是从0->该点的一个路径值，w[下标]则是这个点到另一个点的权值。
• w[i]记录的是x->y的权值，0->x的权值由优先级队列记录first，x是当前桶号，y就可以由e[i]标识。

#include
using namespace std;
#include
#include
const int N = 150010;
//注意 N， M的区别
int h[N],e[N],ne[N],idx = 0;
int w[N];
int dist[N];
bool st[N]; // 如果为true说明这个点的最短路径已经确定

typedef pair<int,int> PII; //先比较权值，在比较边<权值，边>

//x为起始点，y为终点，z为权值
void add(int x ,int y,int z)
{
    //往n这个桶当中插入值权值未x的元素
    e[idx] = y;//存dst
    w[idx] = z;//存权值
    ne[idx] = h[x];//存next值
    h[x] = idx;//存具体的桶
    
    ++idx;
}
int Dijkstra(int n)
{
    //观察桶是否有问题
    // for(int i = 0;i < n; ++ i)
    // {
    //     for(int j = h[i]; j != -1 ;j = ne[j])
    //     {
    //         cout << e[j] << " ";
    //     }
    //     cout << endl;
    // }
    priority_queue<PII,vector<PII>,greater<PII>> pq;
    pq.push({0,0}); //第一个是权值，因为需要先比较权值，而第二个谁靠前不重要。
    dist[0] = 0;
    while(!pq.empty())
    {
        //O(1)获得一个最小的边
        PII p = pq.top();
        pq.pop();
        //更新p点相连的所有点
        
        
        int src = p.second;//对边，一开始是0
        //cout <
        int distance = p.first;
        if(st[src]) continue;
        st[src] = true;
        //从链表的头开始取数据
        for(src = h[src] ;src != -1 ; src = ne[src])
        {
            //cout<< src  << endl;
            //更新对端，dst的内容
            int dst = e[src];//获取对端
            if(w[src] + distance < dist[dst])
            {
                dist[dst] = w[src] + distance;
                pq.push({dist[dst],dst});
            }
        }
    }
    if(dist[n - 1] == 0x3f3f3f3f)
    {
        return -1;
    }
    else
    {
        return dist[n - 1];
    }
    
}
int main()
{
    int n,m;
    cin >> n >> m;
    memset(dist,0x3f,sizeof(dist));//初始化距离矩阵
    memset(h,-1,sizeof(h));//初始化链表头
    while(m --)
    {
        int x,y,z;
        cin >> x >> y >> z;
        add(x - 1,y - 1,z);
    }
    int res = Dijkstra(n);
    cout << res << 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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

---

end

• 喜欢就收藏
• 认同就点赞
• 支持就关注
• 疑问就评论