python/TangDou/AcWing/ShortestPath/850.md

##[$AcWing$ $850$. $Dijkstra$求最短路 $II$](https://www.acwing.com/problem/content/description/852/)
### 一、题目描述
给定一个 $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^5$,图中涉及边长均不小于 $0$，且不超过 $10000$。
数据保证：如果最短路存在，则最短路的长度不超过 $10^9$。

### 二、解题思路

此题与 [$Dijkstra$求最短路$I$](https://www.cnblogs.com/littlehb/p/15316432.html) 有什么本质上的区别？

- 两者$m$(边的数量)的数据范围基本一致，$I$是$10^5$,$II$是$1.5*10^5$，是一个数量级的

- $n$(结点数量)有明显区别：$I$是$500$上限，$II$是$1.5 * 10^5$。可以采用小顶堆对朴素版本的$Dijkstra$进行一次优化。


### 三、实现代码
```cpp {.line-numbers}
#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int N = 150010, M = N << 1;

int st[N];
int dis[N]; // 距离数组

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

int n, m;
int dijkstra() {
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> q; // 小顶堆
    q.push({0, 1});

    while (q.size()) {
        PII t = q.top();
        q.pop();
        int u = t.second;
        if (!st[u]) {
            st[u] = 1;
            for (int i = h[u]; ~i; i = ne[i]) {
                int v = e[i];
                if (dis[v] > dis[u] + w[i]) {
                    dis[v] = dis[u] + w[i];
                    q.push({dis[v], v});
                }
            }
        }
    }
    if (dis[n] == INF) return -1;
    return dis[n];
}
int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    printf("%d\n", dijkstra());
    return 0;
}
```

### 四、问题集
*  **$Q1$:优先队列的数据类型应该是怎样的呢？**
$A$:我们知道优先队列应该用于快速寻找距离最近的点。由于优先队列只是将最小的那个元素排在前面，因此我们应该定义一种数据类型，使得它包含该节点的编号以及该节点当前与起点的距离。
<br>
* **$Q2:$如果一个结点到起点的最短距离可以随多个中间点的加入而变化，那不是加入队列多次吗，如何处理队列中的那个已经存入的元素？**
$A$:事实上，不需要理会队列中的元素，而是再存入一个就行了。因为如果要发生变化，只能将节点与起点之间的距离变得更小，而优先队列恰好是先让最小的那个弹出。
因此，轮到某一个队列元素弹出的时候，如果有多个元素的节点编号相同，那么被弹出的一定是节点编号最小的一个。等到后面再遇到这个节点编号的时候，我们只需要将它忽略掉就行了。
<br>
* **$Q3$:$849$与$850$的代码互通吗？**
$A$:因为$850$使用的是邻接表，而$849$使用的是邻接矩阵，所以，$850$的代码兼容性更强，支持更多的结点数，可以$AC$掉$849$，但反过来就不行了，$849$的代码会因为开不了$1.5*10^5*1.5*10^5$而导致开不出来二维矩阵，无法运行。