## $Dijkstra$算法专题

### 一、解决的问题
计算从 **源** 到所有其他各顶点的最短路径长度。这里的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。

### 二、算法原理
![](https://dsideal.obs.cn-north-1.myhuaweicloud.com/HuangHai/BlogImages/202312180745532.png)

> **视频讲解** : **[【5分钟搞定$Dijkstra$算法】](https://www.bilibili.com/video/BV1ha4y1T7om)**

### 三、题单
#### 【模板题】[$AcWing$ $850$. $Dijkstra$求最短路 $II$](https://www.acwing.com/problem/content/description/852/) 

输入样例
```cpp {.line-numbers}
3 3
1 2 2
2 3 1
1 3 4
```
输出样例
```cpp {.line-numbers}
3
```
**$Code$**
```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;
}
```

### [$AcWing$ $1129$. 热浪](https://www.acwing.com/problem/content/description/1131/)
与模板相比，只是起点和终点是输入的，其它无区别。

**输入样例**：
```cpp {.line-numbers}
7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1
```

**输出样例**：
```cpp {.line-numbers}
7
```


**$Code$**
```cpp {.line-numbers}
#include <bits/stdc++.h>
using namespace std;
const int N = 2510;
const int M = 6200 * 2 + 10;

typedef pair<int, int> PII;

int h[N], w[M], e[M], ne[M], idx;
bool st[N];
int dis[N];

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

int n, m, S, T;

int dijkstra() {
    memset(dis, 0x3f, sizeof dis);
    dis[S] = 0;

    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push({0, S});
    while (q.size()) {
        PII t = q.top();
        q.pop();
        int u = t.second;
        if (st[u]) continue;
        st[u] = true;
        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});
            }
        }
    }
    return dis[T];
}

int main() {
    cin >> n >> m >> S >> T;
    memset(h, -1, sizeof h);

    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    printf("%d\n", dijkstra());
    return 0;
}
```

#### [$AcWing$ $1128$. 信使](https://www.acwing.com/problem/content/1130/)
**总结**：从$1$号哨所出发，计算出到每个哨所的最短路径，所以最短路径中最长的，表示需要的最少时间，是一个最短路径模板+思维问题。

**输入样例**：
```cpp {.line-numbers}
4 4
1 2 4
2 3 7
2 4 1
3 4 6
```

**输出样例**：
```cpp {.line-numbers}
11
```

**$Code$**

```cpp {.line-numbers}
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int N = 110;
const int M = 2 * 210; // 无向图，需要开二倍的数组长度！

int n, m;
int h[N], e[M], w[M], ne[M], idx;
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int dis[N];
bool st[N];

int dijkstra() {
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;

    priority_queue<PII, vector<PII>, greater<int>> q;
    q.push({0, 1});

    while (q.size()) {
        PII t = q.top();
        q.pop();
        int u = t.second;
        if (st[u]) continue;
        st[u] = true;

        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});
            }
        }
    }
    int mx = 0;
    for (int i = 1; i <= n; i++) {
        if (dis[i] == INF) return -1;
        mx = max(mx, dis[i]);
    }
    return mx;
}
int main() {
    memset(h, -1, sizeof h);
    cin >> n >> m;
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    printf("%d\n", dijkstra());
    return 0;
}

```

#### [$AcWing$ $1127$. 香甜的黄油](https://www.acwing.com/problem/content/1129/)

**总结**：本题不是有固定的起点和终点，是起点不一定是哪个。我们需要枚举每一个点做为起点，然后计算每个点作为起点时，消耗的总的边权和，也是代价值。最后比较一下最小的代价值，可以找出哪个点作为起点是最好的选择。

**输入样例**：
```cpp {.line-numbers}
3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5
```

**输出样例**：
```cpp {.line-numbers}
8
```

**$Code$**
```cpp {.line-numbers}
#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> PII;
const int N = 810;  // 牧场数 上限800
const int M = 3000; // 牧场间道路数 上限1450，无向图开双倍
const int INF = 0x3f3f3f3f;
// 邻接表
int h[N], e[M], w[M], ne[M], idx;
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int n, p, m; // 三个数：奶牛数 ，牧场数 ，牧场间道路数
int id[N];   // 每只奶牛在哪个牧场
int dis[N];  // 记录起点到任意点的最短路径
bool st[N];  // 标识每个牧场是否入过队列

int dijkstra(int S) {
    memset(st, 0, sizeof st);
    memset(dis, 0x3f, sizeof dis);
    dis[S] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push({0, S});

    while (q.size()) {
        PII t = q.top();
        q.pop();

        int u = t.second;
        if (st[u]) continue;
        st[u] = true;

        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});
            }
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i++) {     // 遍历每只奶牛
        int j = id[i];                 // j号牧场
        if (dis[j] == INF) return INF; // 如果j号牧场失联了，则无法获得结果
        res += dis[j];                 // 累加一个最小距离
    }
    return res; // 整体的最小距离
}
int main() {
    memset(h, -1, sizeof h);
    cin >> n >> p >> m;                        // 奶牛数，牧场数，牧场间道路数
    for (int i = 1; i <= n; i++) cin >> id[i]; // 1 到 N 头奶牛所在的牧场号

    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    int ans = INF;

    // 枚举每个牧场为出发点，计算它的最短距离和　中的最小值
    for (int i = 1; i <= p; i++) ans = min(ans, dijkstra(i));

    printf("%d\n", ans);
    return 0;
}
```

#### [$AcWing$ $1126$. 最小花费](https://www.acwing.com/problem/content/1128/)

假设初始金钱为$N$,那么如果要在最后一个人的手里得到$100$元，可得公式：
$$\large N∗(1−z_1\%)∗(1−z_2\%)∗…∗(1−z_n\%)=100$$

$\Rightarrow$ 
$$\large N=\frac{100}{(1−z_1\%)∗(1−z_2\%)∗…∗(1−z_n\%)}$$

要想$N$尽可能小，那么就要让 **分母尽可能大** ，即求$(1−z_1\%)∗(1−z_2\%)∗…∗(1−z_n\%)$的最大值。

**输入样例**：
```cpp {.line-numbers}
3 3
1 2 1
2 3 2
1 3 3
1 3
```

**输出样例**：
```cpp {.line-numbers}
103.07153164
```

**$Code$**
```cpp {.line-numbers}
#include <bits/stdc++.h>
using namespace std;

const int N = 2010;
const int M = 2e5 + 10;

typedef pair<double, int> PDI; // 堆中数值是浮点数，注意区别

int n, m;
double dis[N];
bool st[N];

int h[N], e[M], ne[M], idx;
double w[M]; // 边权为浮点数,与一般的题目有区别
void add(int a, int b, double c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int S, T;
void dijkstra() {
    priority_queue<PDI> q; // 大顶堆
    dis[S] = 1;
    q.push({1, S});

    while (q.size()) {
        auto t = q.top();
        q.pop();
        int u = t.second;
        if (st[u]) continue;
        st[u] = true;

        for (int i = h[u]; ~i; i = ne[i]) {
            int v = e[i];
            double a = 1 - w[i];
            if (dis[v] < dis[u] * a) {
                dis[v] = dis[u] * a;
                q.push({dis[v], v});
            }
        }
    }
}

int main() {
    memset(h, -1, sizeof h);
    cin >> n >> m;

    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        double w = c * 0.01;
        add(a, b, w), add(b, a, w);
    }

    cin >> S >> T;

    dijkstra();
    printf("%.8lf\n", 100 / dis[T]);
    return 0;
}
```

#### [$AcWing$ $920$. 最优乘车](https://www.acwing.com/problem/content/922/)

**总结**：
① 建图是本题的关键！同一趟车，不管走几站，走多远，花多少钱，都算是同一趟车，边权都是$1$!
② 本题的输入也是一大特点，每趟车不知道具体有几站，只知道换行算结束，需要学习读入办法。

```cpp {.line-numbers}
#include <bits/stdc++.h>

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

const int N = 1e5 + 10, M = N << 1;

int n; // 总共有N个车站
int m; // 开通了M条单程巴士线路
int h[N], e[M], w[M], ne[M], idx;
int dis[N]; // 最小距离数组
bool st[N]; // 是否在队列中

int stop[N]; // 站点数组

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
void dijkstra() {
    memset(dis, 0x3f, sizeof dis);                    // 求最小设最大
    dis[1] = 0;                                       // 1到自己，乘车数0
    priority_queue<PII, vector<PII>, greater<PII>> q; // 小顶堆
    q.push({0, 1});                                   // 1号入队列

    while (q.size()) {
        auto t = q.top();
        q.pop();
        int u = t.second;
        if (st[u]) continue;
        st[u] = true;
        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});
            }
        }
    }
}

int main() {
    memset(h, -1, sizeof h); // 初始化邻接表
    cin >> m >> n;           // 总共有N个车站,开通了M条单程巴士线路
    while (m--) {            // m条边
        // ① 先读入第一个数字
        int cnt = 0; // cnt一定要清零
        cin >> stop[++cnt];
        char ch = getchar();
        while (ch == ' ') {
            // ② 读入其它数字
            cin >> stop[++cnt]; // 还有就继续读
            ch = getchar();     // 为下一次做准备
        }
        // 这个建图建的妙啊！
        // 通过多条边，成功映射了问题，将一趟车问题转化为多个点之间边是1问题
        for (int i = 1; i <= cnt; i++)
            for (int j = i + 1; j <= cnt; j++)
                add(stop[i], stop[j], 1);
    }

    dijkstra();
    if (dis[n] == INF)
        puts("NO");
    else
        printf("%d\n", dis[n] - 1);
    return 0;
}
```
####  [$AcWing$ $903$. 昂贵的聘礼](https://www.acwing.com/problem/content/905/)

**建图方式**

假入我们想要$A$物品，而$A$物品的原价是$w_1$元，如果有$B$物品作为交换的话，只需要$c_1$元就可以得到$A$物品，那我们不就相当于$B$物品和$c_1$元可以得到$A$物品,也就是等价于$B$到$A$的路径为$c_1$吗？

那每个物品的原价我们又该怎么处理呢？这里在建图上有一个特殊的技巧：建立一个 <font color='red' size=4><b>超级源点</b></font> $O$! 
$O$到每个物品的距离就是物品的原价，而我们需要不断地交换来降低我们想要获得物品的花费，这就是一个最短路问题了。

* 每个点 $i$ 的价格 相当于 从点$0$到点 $i$ **连一条边**, **边权** 定义为点$i$的价格
* 每个点 $i$ 有多个可替代点: **从可替代点** 到点$i$ **连一条边**
* **结果**:顶点 $0$ 到 顶点 $1$ 的 **最短路**

<center><img src='https://img2022.cnblogs.com/blog/8562/202203/8562-20220315104736167-544730696.png'></center>


**等级限制**

* 酋长的女儿肯定是要娶到手的，所有的路径都会汇集在 $1$ 号点，也就是说 $1$ 号点是所有路径中都存在的点

* 假设 $1$号点等级为 $L_1$，则所有最短路的点都必须满足在 $[L_1-M,L_1+M]$ 范围内

* 如果只是将$[L_1-M,L_1+M]$ 这个区间作为最后的区间，会存在两个点的等级差超过了 $M$ 值，不符合题意，所以，这个区间还要继续缩小

依次枚举区间 $[L_1-M,L_1],[L_1-M+1,L_1+1],[L_1-M+2,L_1+2]...[L_1,L_1+M]$，这些小区间内的任意两个点的等级都不会超过 $M$ 值，并且同时保证了 $1$ 号点肯定在区间内。

因此，**依次求出每个小区间的最短路，最后再取最小值就是答案**



```cpp {.line-numbers}
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
const int M = N * N; // 边数最多有n^2,这是顶天设置，此处与传统的题目不，一般的M=　N<<1，此题目没有明确给出边数上限，直接认为N^2
const int INF = 0x3f3f3f3f;

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

int dis[N]; // 单源最短路径
bool st[N]; // 配合Dijkstra用的是否出队过

int L[N]; // 每个节点的等级
int n, m; // n个物品，m表示等级差距限制

int dijkstra(int l, int r) {
    memset(dis, 0x3f, sizeof dis);
    memset(st, 0, sizeof st);
    priority_queue<PII, vector<PII>, greater<PII>> q;
    // 距离，节点号
    q.push({0, 0}); // 超级源点
    dis[0] = 0;

    while (q.size()) {
        auto t = q.top();
        q.pop();
        int u = t.second;
        if (st[u]) continue;
        st[u] = true;

        for (int i = h[u]; ~i; i = ne[i]) {
            int v = e[i];
            // 枚举边时，只处理等级在指定范围内
            if (L[v] < l || L[v] > r) continue;

            if (dis[v] > dis[u] + w[i]) {
                dis[v] = dis[u] + w[i];
                q.push({dis[v], v});
            }
        }
    }
    return dis[1];
}

int main() {
    memset(h, -1, sizeof h); // 初始化邻接表
    cin >> m >> n;           // m:表示地位等级差距限制，n:物品的总数

    for (int i = 1; i <= n; i++) { // 枚举每个节点
        int p, l, cnt;             // 价格 等级 替代品数目
        cin >> p >> L[i] >> cnt;

        add(0, i, p); // 虚拟源点0,　0获取i号物品，需要p这么多的金币

        while (cnt--) {    // 读入物品i的替代品
            int u, v;      // 替代品的编号 和 优惠价格
            cin >> u >> v; // u:替代品编号，v:收到替代品后的收费价格
            add(u, i, v);  // 从替代品向可替代品引一条长度为v的边
        }
    }
    // 预求最小，先设最大
    int res = INF;
    // 枚举区间范围进行多次求最小路径
    for (int i = L[1] - m; i <= L[1]; i++)
        res = min(res, dijkstra(i, i + m));
    // 输出结果
    cout << res << endl;
    return 0;
}
```

#### [$AcWing$ $1135$. 新年好](https://www.acwing.com/problem/content/1137/)

### 一、题目描述
重庆城里有 $n$ 个车站，$m$ 条 **双向** 公路连接其中的某些车站。

每两个车站 **最多** 用一条公路连接，从任何一个车站出发都可以经过一条或者多条公路到达其他车站，但不同的路径需要花费的时间可能不同。

在一条路径上花费的时间等于路径上所有公路需要的时间之和。

佳佳的家在车站 $1$，他有五个亲戚，分别住在车站 $a,b,c,d,e$。

过年了，他需要从自己的家出发，拜访每个亲戚（顺序任意），给他们送去节日的祝福。

怎样走，**才需要最少的时间**？

**输入格式**
第一行：包含两个整数 $n,m$，分别表示车站数目和公路数目。

第二行：包含五个整数 $a,b,c,d,e$，分别表示五个亲戚所在车站编号。

以下 $m$ 行，每行三个整数 $x,y,t$，表示公路连接的两个车站编号和时间。

**输出格式**
输出仅一行，包含一个整数 T，表示最少的总时间。

**数据范围**
$1≤n≤50000,1≤m≤10^5,1<a,b,c,d,e≤n,1≤x,y≤n,1≤t≤100$

**输入样例**：
```cpp {.line-numbers}
6 6
2 3 4 5 6
1 2 8
2 3 3
3 4 4
4 5 5
5 6 2
1 6 7
```

输出样例：
```cpp {.line-numbers}
21
```
#### 1. 梳理概念
**车站**: $1,2,3,4,5,6,7,...,50000$，最多可能$50000$个 
<font color='red' size=4><b>这个数量挺大</b></font>

**亲戚个数**：$5$个，分别住 $a,b,c,d,e$号车站 
<font color='red' size=4><b>这个数量挺小，看来可以利用一下</b></font>

**亲戚家与车站关联关系**
$id[1]=8$ 表示第$1$个亲戚家住在$8$号车站附近,记录每个亲戚与车站的关系


#### 2、思考过程
① 必须由佳佳的家出发，也就是出发点肯定是$1$号车站
② 现在想求佳佳去$5$个亲戚家,每一家都需要走到，不能漏掉任何一家，但顺序可以任意。这里要用一个关系数组$id[]$来把亲戚家的编号与车站号挂接一下。
③ 看到是最短路径问题，而且权值是正整数，考虑$Dijkstra$。
④ 但$Dijkstra$只能是单源最短路径求解，比如佳佳去二姨家，最短路径是多少。佳佳去三舅家，最短路径是多少。本题不是问某一家，问的是佳佳全去到，总的路径和最短是多少，这样的话，直接使用$Dijkstra$就无效了。
⑤ 继续思考:因为亲戚家只有$5$个,可以从这里下手，通过全排列的办法，枚举出所有的可能顺序，此时，计算次数=$5*4*3*2*1=120$次。
⑥ 跑多次$Dijkstra$是在干什么呢？就是在分别以二姨，三舅，四大爷家为出发点，分别计算出到其它亲戚家的最短距离，如果我们把顺序分别枚举出来，每次查一下已经预处理出来的两个亲戚家的最短距离，再加在一起，不就是可以进行$PK$最小值了吗？

至此，整体思路完成。

![](https://dsideal.obs.cn-north-1.myhuaweicloud.com/HuangHai/BlogImages/202312281603744.png)

#### 3.编码步骤

* **$6$次最短路**
  分别以佳佳家、五个亲戚家为出发点($id[i]~ i\in[0,5]$)，求$6$次最短路，相当于打表，一会要查

* **求全排列**
  因为佳佳所有的亲戚都要拜访到，现在不知道的是什么样顺序拜访才是时间最少的。 把所有可能顺序都 **枚举** 出来，通过查表，找出两个亲戚家之间的最小时间，累加结果的和，再$PK$最小就是答案

#### 4.实现细节
通过前面的$6$次打表预处理，可以求出$6$个$dist$数组，当我们需要查找 $1->5$的最短路径时，直接查$dist[1][5]$

$dist[i][j]$:从$i$号亲戚家(不是$i$号车站)出发，到达每个车站站点的 **最短距离**

<font color='red' size=4><b>注意:</b></font>
这两个维度在概念上这所以存在差异，本质上是为了防止$MLE$:
如果第一维也是车站站点的话，就是$50000*50000$的二维矩阵，$≈2.5e9$,大的吓人。因为我们只关心从这$6$个位置出发的所有最短距离，所以第一维开成$0$~$5$。现在的空间占用是 $50000*6=300000$,也就是$3e5$

$\large Code$
```cpp {.line-numbers}
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;

const int N = 50010;       // 车站数目
const int M = N << 1 << 1; // 公路数目，一般来说，N个节点，通常是2*N条边，如果是无向图，再乘2
const int INF = 0x3f3f3f3f;

int n, m; // 车站数目,公路数目

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

int dis[6][N];
int id[6]; // 0号索引：佳佳的家,其它5个亲戚，分别下标为1~5，值为所在的车站编号

/*
1、用在Dijkstra中判断量不是出过队列，多次调用Dijkstra需要在函数体内进行状态重置　
2、在dfs求全排列时，需要清空后记录在此路线上此　亲戚号　是不是走过了
*/
bool st[N];

/*
 S:出发车站编号
 dis[]:是全局变量dis[6][N]的某一个二维，其实是一个一维数组
 C++的特点：如果数组做参数传递的话,将直接修改原地址的数据
 此数组传值方式可以让我们深入理解C++的二维数组本质：就是多个一维数组，给数组头就可以顺序找到其它相关数据
 计算的结果：获取到S出发到其它各个站点的最短距离，记录到dis[S][站点号]中
*/
void dijkstra(int S, int dis[]) {
    dis[S] = 0;
    memset(st, false, sizeof st);
    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push({0, S});

    while (q.size()) {
        auto t = q.top();
        q.pop();
        int u = t.second;
        if (st[u]) continue;
        st[u] = true;
        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});
            }
        }
    }
}

int ans = INF; // 预求最小先设最大

// u:第几个亲戚
// pre:前序站点
// sum:按此路径走的总距离和
void dfs(int u, int pre, int sum) {
    if (u == 6) { // 如果安排完所有亲戚的拜访顺序，就是得到了一组解，尝试更新最小值
        ans = min(ans, sum);
        return;
    }
    for (int i = 1; i <= 5; i++) // 在当前位置上，枚举每个可能出现在亲戚站点
        if (!st[i]) {            // 如果这个亲戚没走过
            st[i] = true;        // 走它
            // 本位置填充完，下一个位置，需要传递前序是i,走过的路径和是sum+dis[pre][id[i]].因为提前打好表了，所以肯定是最小值，直接用就行了　
            // 需要注意的是一维是　6的上限，也就是　佳佳家+五个亲戚　，而不是 车站号(佳佳家+五个亲戚) !因为这样的话，数据就很大，数组开起来麻烦，可能会MLE
            // 要注意学习使用小的数据标号进行事情描述的思想
            dfs(u + 1, i, sum + dis[pre][id[i]]);
            st[i] = false; // 回溯
        }
}

int main() {
    scanf("%d %d", &n, &m); // 车站数目和公路数目

    id[0] = 1;                                        // 佳佳是0，id[0]=1,表示佳佳家在1号车站
    for (int i = 1; i <= 5; i++) scanf("%d", &id[i]); // 五个亲戚所在车站编号,比如id[1]=2,描述1号亲戚在2号车站

    // 建图完成后，图中的节点其实是　车站的站点编号，而不是亲戚编号
    memset(h, -1, sizeof h); // 为了存图，需要初始化邻接表

    while (m--) { // 建图
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c); // a号车站到b号车站，需要走的时间是c
        add(a, b, c), add(b, a, c);    // 无向图，双向建边
    }

    // 计算从某个亲戚所在的车站出发，到达其它几个点的最短路径
    // 因为这样会产生多组最短距离，需要一个二维的数组进行存储
    memset(dis, 0x3f, sizeof dis);
    for (int i = 0; i < 6; i++) dijkstra(id[i], dis[i]);
    // 枚举每个亲戚所在的车站站点，多次Dijkstra,分别计算出以id[i]这个车站出发，到达其它点的最短距离，相当于打表
    // 将结果距离保存到给定的二维数组dis的第二维中去，第一维是指从哪个车站点出发的意思

    // dfs还要用这个st数组做其它用途，所以，需要再次的清空
    memset(st, 0, sizeof st);

    // 1：准备走第一家亲戚(具体是a,b,c,d,e哪一家随意都可以)
    // 0：前序是佳佳自己家,他自己家的序号是0号
    // 0：已经走过的最短距离和是0
    dfs(1, 0, 0);

    // 　输出结果
    printf("%d\n", ans);
    return 0;
}
```
#### [$AcWing$ $340$. 通信线路](https://www.acwing.com/problem/content/342/)
### 一、题目描述
在郊区有 $N$ 座通信基站，$P$ 条 **双向** 电缆，第 $i$ 条电缆连接基站 $A_i$ 和 $B_i$。

特别地，**$1$号基站是通信公司的总站** (起点)，**$N$号基站** (终点) 位于一座农场中。

现在，农场主希望对通信线路进行升级，其中升级第 $i$ 条电缆需要花费 $L_i$

电话公司正在举行优惠活动

农产主可以指定一条从 $1$ 号基站到 $N$ 号基站的路径，并指定路径上不超过 $K$ 条电缆，由电话公司 **免费** 提供升级服务

农场主只需要支付在该路径上 **剩余的电缆中**，**升级价格最贵** 的那条电缆的花费即可

求 **至少用多少钱** 可以完成升级


**输入格式**
第 $1$ 行：三个整数 $N，P，K$。

第 $2..P+1$ 行：第 $i+1$ 行包含三个整数 $A_i,B_i,L_i$。

**输出格式**
包含一个整数表示最少花费。

若 $1$ 号基站与 $N$ 号基站之间不存在路径，则输出 $−1$。


**数据范围**
$0≤K<N≤1000,1≤P≤10000,1≤L_i≤1000000$

**输入样例**：
```cpp {.line-numbers}
5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6
```

**输出样例**：
```cpp {.line-numbers}
4
```

![](https://dsideal.obs.cn-north-1.myhuaweicloud.com/HuangHai/BlogImages/%7Byear%7D/%7Bmonth%7D/%7Bmd5%7D.%7BextName%7D/20230705095514.png)


### 二、题目解析

#### 理解题意
找一条路径，边权最大的$k$条边忽略，**第$k + 1$大的边权作为该条路径的代价**，**求最小代价**


#### 思考过程 

① 从$1$号点出发，没有路可以到达$n$点, **无解**，输出$-1$

② 如果 **最短路径边数**（**注意：不是路径的加权和**）不超过$k$条，含义：不用花钱就可以升级线路, 输出$0$

③ 上面 ②中给我们提出了一个新概念：**路径边数**，我们知道，如果想计算获取 **路径边数**，常见的办法是设置边权为$1$。 那是不是所有边都设置为边权为$1$呢？好像不行，因为这样的话，那人家还给你修每条路径的钱数就没用上啊，而且你也没有办法求出你的最小支出啊，此路不通。

④ 这就很纠结啊：不设边权为$1$，无法知道路径长度；全设边权为$1$，就会丢失关键信息。只能是设置 **部分** 边权为$1$。

⑤ 那啥样的边权为$1$,啥样的边权为$0$呢？还得用上真实的边权概念！此时，有如下猜想：
> **如果给我$mid$元钱，我有没有办法确定这么多钱能否够完成升级一条线路呢？**
> 这个简单，我们可以视真实边权大于$mid$的设置 **虚拟边权** 为$1$,反之设为$0$
> 然后在这个图上用$Dijkstra$求最短路径，也就是最短路径长度：
>   - 如果最短路径的长度值大于$k$,说明$mid$小了，再调大一点
>   - 如果最短路径的长度值不大于$k$,说明$mid$大了，再调小一点

噢，原来需要 **二分答案**

#### $Code$
```cpp {.line-numbers}
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int N = 1010;  // 1000个点
const int M = 20010; // 10000条，记录无向边需要两倍空间
int idx, h[N], e[M], w[M], ne[M];
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int n; // 点数
int m; // 边数

int k; // 不超过K条电缆，由电话公司免费提供升级服务

bool st[N]; // 记录是不是在队列中
int dis[N]; // 记录最短距离

// mid指的是我们现在选最小花费
bool check(int mid) {
    // 需要跑多次dijkstra，所以需要清空状态数组
    memset(st, false, sizeof st);
    memset(dis, 0x3f, sizeof dis);
    priority_queue<PII, vector<PII>, greater<PII>> q;
    dis[1] = 0;
    q.push({0, 1});

    while (q.size()) {
        PII t = q.top();
        q.pop();
        int u = t.second;
        if (st[u]) continue;
        st[u] = true;
        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            int v = w[i] > mid; // 如果有边比我们现在选的这条边大，那么这条边对方案的贡献为1，反之为0
            if (dis[j] > dis[u] + v) {
                dis[j] = dis[u] + v;
                q.push({dis[j], j});
            }
        }
    }
    // 如果按上面的方法计算后，n结点没有被松弛操作修改距离，则表示n不可达
    if (dis[n] == INF) {
        puts("-1"); // 不可达，直接输出-1
        exit(0);
    }
    return dis[n] <= k; // 如果有k+1条边比我们现在这条边大，那么这个升级方案就是不合法的，反之就合法
}
int main() {
    memset(h, -1, sizeof h);
    cin >> n >> m >> k;
    int a, b, c;
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    /*
    这里二分的是直接面对答案设问： 至少用多少钱 可以完成升级
    依题意，最少花费其实是所有可能的路径中，第k+1条边的花费
    如果某条路径不存在k+1条边(边数小于k+1),此时花费为0
    同时，任意一条边的花费不会大于1e6,所以,这里二分枚举范围:0 ~ 1e6
    */
    int l = 0, r = 1e6;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(mid)) // check函数的意义：如果当前花费可以满足要求，那么尝试更小的花费
            r = mid;
        else
            l = mid + 1;
    }
    printf("%d\n", l);
    return 0;
}
```

## [$AcWing$ $342$ 道路与航线](https://www.acwing.com/problem/content/description/344/)

### 一、题目描述
农夫约翰正在一个新的销售区域对他的牛奶销售方案进行调查。

他想把牛奶送到 $T$ 个城镇，编号为 $1$∼$T$。

这些城镇之间通过 $R$ 条道路 (编号为 $1$ 到 $R$) 和 $P$ 条航线 (编号为 $1$ 到 $P$) 连接。

每条道路 $i$ 或者 航线 $i$ 连接城镇 $A_i$ 到 $B_i$，花费为 $C_i$。

对于道路，$0≤C_i≤10,000$;然而航线的花费很神奇，花费 $C_i$ 可能是负数$(−10,000≤Ci≤10,000)$。

**道路是双向的**，可以从 $A_i$ 到 $B_i$，也可以从 $B_i$ 到 $A_i$，花费都是 $C_i$。

然而 **航线与之不同**，只可以从 $A_i$ 到 $B_i$。

事实上，由于最近恐怖主义太嚣张，为了社会和谐，出台了一些政策：
<font color='red' size=4><b>
保证如果有一条航线可以从 $A_i$ 到 $B_i$，那么保证不可能通过一些道路和航线从$B_i$ 回到 $A_i$。
</b></font>

由于约翰的奶牛世界公认十分给力，他需要运送奶牛到每一个城镇。

他想找到从发送中心城镇 $S$ **把奶牛送到每个城镇的最便宜的方案**。

**输入格式**
第一行包含四个整数 $T,R,P,S$。

接下来 $R$ 行，每行包含三个整数（表示一个道路）$A_i,B_i,C_i$。

接下来 $P$ 行，每行包含三个整数（表示一条航线）$A_i,B_i,C_i$。

**输出格式**
第 $1..T$ 行：第 $i$ 行输出从 $S$ 到达城镇 $i$ 的最小花费，如果不存在，则输出 `NO PATH`。

### 二、$Dijkstra$不能处理负权边
我们说了$Dijkstra$算法不能解决带有负权边的图，这是为什么呢？下面用一个例子讲解一下
![](https://img-blog.csdnimg.cn/51115e15bd3040d7a8b3980b523ed943.png)

以这里图为例，一共有五个点，也就说要循环$5$次，确定每个点的最短距离

用$Dijkstra$算法解决的的详细步骤
> 1. 初始$dis[1] = 0$，$1$号点距离起点$1$的距离为$0$
> 2. 找到了未标识且离起点$1$最近的结点$1$，标记$1$号点，用$1$号点更新和它相连点的距离，$2$号点被更新成$dis[2] = 2$，$3$号点被更新成$dis[3] = 5$
> 3. 找到了未标识且离起点$1$最近的结点$2$，标识$2$号点，用$2$号点更新和它相连点的距离，$4$号点被更新成$dis[4] = 4$
> 4. 找到了未标识且离起点$1$最近的结点$4$，标识$4$号点，用$4$号点更新和它相连点的距离，$5$号点被更新成$dis[5] = 5$
> 5. 找到了未标识且离起点$1$最近的结点$3$，标识$3$号点，用$3$号点更新和它相连点的距离，$4$号点被更新成$dis[4] = 3$
> 

**结果**
> $Dijkstra$算法在图中走出来的最短路径是$1 -> 2 -> 4 -> 5$，算出 $1$ 号点到$5$ 号点的最短距离是$2 + 2 + 1 = 5$，然而还存在一条路径是$1 -> 3 -> 4 -> 5$，该路径的长度是$5 + (-2) + 1 = 4$
> 因此 $dijkstra$ 算法 **失效**

**总结**
> 我们可以发现如果有负权边的话$4$号点经过标记后还可以继续更新
但此时$4$号点已经被标记过了，所以$4$号点不能被更新了，只能一条路走到黑
当用负权边更新$4$号点后$5$号点距离起点的距离我们可以发现可以进一步缩小成$4$。  
所以总结下来就是:$dijkstra$ **不能解决负权边** 是因为 $dijkstra$要求每个点被确定后，$dis[j]$就是最短距离了，之后就不能再被更新了（**一锤子买卖**），而如果有负权边的话，那已经确定的点的$dis[j]$不一定是最短了，可能还可以通过负权边进行更新。


### 三、拓扑序+$Dijkstra$ + 缩点

* ① 分析题目可知城镇内部之间的权值是非负的，内部可以使用$dijkstra$算法
* ② 城镇之间的航线 **有负权**，不能用$Dijkstra$。虽然$SFPA$可以搞定负权，但记住它已经死了，不考虑它~
* ③ 如果有严格的顺序关系，即拓扑序，按照 **城镇拓扑序的关系**,是可以使用$Dijkstra$的，原因如下：
  每个城镇称为一个 **团**，按照 **拓扑序** 遍历到某个团时，**此时该团中城市的距离不会再被其它团更新**，因此可以 **按照拓扑序** **依次** 运行 $dijkstra$ 算法


<center><img src='https://cdn.acwing.com/media/article/image/2021/07/12/61813_4db65cc0e2-image-20210323150329169.png'></center>

#### 算法步骤
<center><img src='https://cdn.acwing.com/media/article/image/2021/07/12/61813_53a888d8e2-image-20210323144423779.png'></center>

扩展：用拓扑排序解决dag带负权图的最短路问题
![](https://dsideal.obs.cn-north-1.myhuaweicloud.com/HuangHai/BlogImages/202312291324775.png)

#### $Code$
```cpp {.line-numbers}
#include <bits/stdc++.h>
using namespace std;
const int N = 25010, M = 150010;
const int INF = 0x3f3f3f3f;

typedef pair<int, int> PII;

// 存图
int idx, h[N], e[M], w[M], ne[M];
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int T; // 城镇数量
int R; // 道路数量
int P; // 航线数量
int S; // 出发点

// 下面两个数组是一对
int id[N];            // 节点在哪个连通块中
vector<int> block[N]; // 连通块包含哪些节点
int bcnt;             // 连通块序号计数器

int dis[N];   // 最短距离(结果数组)
int in[N];    // 每个DAG(节点即连通块)的入度
bool st[N];   // dijkstra用的是不是在队列中的数组
queue<int> q; // 拓扑序用的队列

// 将u节点加入团中,团的番号是 bid
void dfs(int u, int bid) {
    id[u] = bid;             // ① u节点属于bid团
    block[bid].push_back(u); // ② 记录bid团包含u节点
    // 枚举u节点的每一条出边，将对端的城镇也加入到bid这个团中
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (!id[j]) dfs(j, bid); // Flood Fill
    }
}

// 计算得到bid这个连通块中最短距离
void dijkstra(int bid) {
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    /*
    因为不确定连通块内的哪个点可以作为起点，所以就一股脑全加进来就行了，
    反正很多点的dis都是inf（这些都是不能成为起点的）,那么可以作为起点的就自然出现在堆顶了

    因为上面的写法把拓扑排序和dijkstra算法拼在一起了，如果不把所有点都加入堆，
    会导致后面其他块的din[]没有减去前驱边，从而某些块没有被拓扑排序遍历到。
    */
    for (auto u : block[bid]) pq.push({dis[u], u});

    while (pq.size()) {
        int u = pq.top().second;
        pq.pop();
        if (st[u]) continue;
        st[u] = true;
        for (int i = h[u]; ~i; i = ne[i]) {
            int v = e[i];
            if (st[v]) continue;

            if (dis[v] > dis[u] + w[i]) {
                dis[v] = dis[u] + w[i];
                // 如果是同团中的道路,需要再次进入Dijkstra的小顶堆，以便计算完整个团中的路径最小值
                if (id[u] == id[v]) pq.push({dis[v], v});
            }
            /*如果u和v不在同一个团中,说明遍历到的是航线
             此时，需要与拓扑序算法结合，尝试剪掉此边，是不是可以形成入度为的团

             id[v]:v这个节点所在的团番号
             --in[id[v]] == 0: u->v是最后一条指向团id[v]的边，此边拆除后，id[v]这个团无前序依赖，稳定了，
             可以将此团加入拓扑排序的queue队列中，继续探索
           */
            if (id[u] != id[v] && --in[id[v]] == 0) q.push(id[v]);
        }
    }
}

// 拓扑序
void topsort() {
    for (int i = 1; i <= bcnt; i++) // 枚举每个团
        if (!in[i]) q.push(i);      // 找到所有入度为0的团,DAG的起点

    // 拓扑排序
    while (q.size()) {
        int bid = q.front(); // 团番号
        q.pop();
        // 在此团内部跑一遍dijkstra
        dijkstra(bid);
    }
}

int main() {
    memset(h, -1, sizeof h);              // 初始化
    scanf("%d %d %d %d", &T, &R, &P, &S); // 城镇数量,道路数量,航线数量,出发点

    memset(dis, 0x3f, sizeof dis); // 初始化最短距离
    dis[S] = 0;                    // 出发点距离自己的长度是0,其它的最短距离目前是INF

    int a, b, c; // 起点，终点，权值

    while (R--) { // 读入道路,团内无向图
        scanf("%d %d %d", &a, &b, &c);
        add(a, b, c), add(b, a, c); // 连通块内是无向图
    }

    /* 航线本质是 团与团 之间单向连接边
     外部是DAG有向无环图，局部是内部双向正权图
     为了建立外部的DAG有向无环图，我们需要给每个团分配一个番号，记为bid;
     同时，也需要知道每个团内，有哪些小节点:
     (1) id[i]:节点i隶属于哪个团(需要提前准备好团的番号)
     (2) vector<int> block[N] :每个团中有哪些节点

     Q:一共几个团呢？每个团中都有谁呢？谁都在哪个图里呢？
     A:在没有录入航线的情况下，现在图中只有 大块孤立 但 内部连通 的节点数据，
     可以用dfs进行Flood Fill,发现没有团标识的节点，就创建一个新的团番号，
     并且记录此节点加入了哪个团，记录哪个团有哪些点。
     注意：需要在未录入航线的情况下统计出团与节点的关系，否则一会再录入航线，就没法找出哪些节点在哪个团里了
    */
    // 缩点
    for (int i = 1; i <= T; i++) // 枚举每个小节点
        if (!id[i])              // 如果它还没有标识是哪个团,就开始研究它，把它标识上隶属于哪个团，并且，把和它相连接的其它点也加入同一个团中
            dfs(i, ++bcnt);      // 需要提前申请好番号bcnt

    // 航线
    while (P--) {
        scanf("%d %d %d", &a, &b, &c);
        add(a, b, c); // 单向边
        in[id[b]]++;  // b节点所在团的番号,也就是某个团的入度+1
    }

    // 拓扑
    topsort();

    // 从S到达城镇i的最小花费
    for (int i = 1; i <= T; i++) {
        if (dis[i] > INF / 2)
            puts("NO PATH");
        else
            cout << dis[i] << endl;
    }
    return 0;
}
```

## [$AcWing$ $341$. 最优贸易](https://www.acwing.com/problem/content/description/343/)

### 一、题目描述
$C$ 国有 $n$ 个大城市和 $m$ 条道路，每条道路连接这 $n$ 个城市中的某两个城市。

任意两个城市之间 **最多只有一条道路直接相连**。

这 $m$ 条道路中有一部分为 **单向通行的道路**，一部分为 **双向通行的道路**，双向通行的道路在统计条数时也计为 $1$ 条。

$C$ 国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。

但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。

商人阿龙来到 $C$ 国旅游。

当他得知 **同一种商品在不同城市的价格可能会不同** 这一信息之后，便决定在旅游的同时，利用商品在不同城市中的差价赚一点旅费。

设 $C$ 国 $n$ 个城市的标号从 $1$∼$n$，阿龙决定从 $1$ 号城市出发，并最终在 $n$ 号城市结束自己的旅行。

在旅游的过程中，**任何城市可以被重复经过多次** ，**但不要求经过所有 $n$ 个城市**。

阿龙通过这样的贸易方式赚取旅费：他会 **选择一个经过的城市买入** 他最喜欢的商品——水晶球，并在之后 **经过的另一个城市卖出** 这个水晶球，用赚取的 **差价** 当做旅费。

因为阿龙主要是来 $C$ 国旅游，他决定这个贸易 **只进行最多一次**，当然，在赚不到差价的情况下他就无需进行贸易。

现在给出 $n$ 个城市的水晶球价格，$m$ 条道路的信息（每条道路所连接的两个城市的编号以及该条道路的通行情况）。

请你告诉阿龙，**他最多能赚取多少旅费**。

**注意**：本题数据有 **加强**。

**输入格式**
第一行包含 $2$ 个正整数 $n$ 和 $m$，中间用一个空格隔开，分别表示城市的数目和道路的数目。

第二行 $n$ 个正整数，每两个整数之间用一个空格隔开，按标号顺序分别表示这 $n$ 个城市的商品价格。

接下来 $m$ 行，每行有 $3$ 个正整数，$x，y，z$，每两个整数之间用一个空格隔开。

如果 $z=1$，表示这条道路是城市 $x$ 到城市 $y$ 之间的单向道路；如果 $z=2$，表示这条道路为城市 $x$ 和城市 $y$ 之间的双向道路。

**输出格式**
一个整数，表示答案。

**数据范围**
$1≤n≤100000,1≤m≤500000$,
$1≤$各城市水晶球价格$≤100$

**输入样例**：
```cpp {.line-numbers}
5 5
4 3 5 6 1
1 2 1
1 4 1
2 3 2
3 5 1
4 5 2
```

**输出样例**：
```cpp {.line-numbers}
5
```


### 二、解题思路

**阿龙决定从 $1$ 号城市出发，并最终在 $n$ 号城市结束自己的旅行。**

终点是$n$，但题目并没有保证所有点都能去到点$n$。

要知道哪些点不能去到点$n$，可以 **反向建图**，在这张图以$n$为起点看能到达哪些点。


**分析**： 这道题需要建两个图，一个为 **正向图** ，一个为 **反向图** ，考虑分别跑$Dijkstra$算法得到$dis1$数组和$dis2$数组:

* $dis1[i]$:从点$1$到点$i$的所有路径上经过的 **最小点权**
* $dis2[i]$:从点$n$经过反向边到点$i$的所有路径上经过的 **最大点权**

当求出这两个数组后就可以枚举路径上的 **中间点**$i$，最终答案就是
$$\large max(dis2[i]-dis1[i])$$


**理论** 上这就没问题了，不过这道题目比较特殊，由于图中 **可能出现回路**，且$dis$值是记录 **点权的最值** ，在某些情况下是 **具有后效性**的，如下图： 

<center><img src='https://img-blog.csdnimg.cn/f553c1000eb04000a4fe36692462d41e.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAI-i_meaYr-S4gOadoeazqOmHiuOAgg==,size_20,color_FFFFFF,t_70,g_se,x_16'></center>

**点权** 用绿色数字标示在点号下方，可以发现在点$2$处会经过一个回路再次回到点$2$，但在这之前点$5$的$dis$已经被更新为$3$了
><font color='red' size=3><b>解释：因为$1 \rightarrow 2 \rightarrow 5$这条路线上，在点$2$时，水晶球的价格最便宜，价格是$3$</b></font>

之后回到点$2$，由于$st[2] == true$直接$continue$，虽然此时$dis[2] == 1$但却无法把$1$传递给点$5$了。

<font color='blue' size=4><b>采用办法</b></font>
在$dijkstra$算法中去掉$st$的限制，让整个算法不断迭代，直到无法更新导致队空退出循环。这就类似于$DP$的所有情况尝试，不断刷新最新最小价格！

**总结**
本题用$Dijkstra$的话，其实已经不是传统意义上的$Dijkstra$了，因为它允许出边再进入队列！（去掉了$st$数组 ，因为有环嘛），指望 **更无可更，无需再更**。

**最大最小值**，其实也不是传统最短、最长路的路径累加和，而是类似于$DP$的思路，一路走来一路维护到达当前点的最大点权和最小点权。

**配合$DP$**
严格意义上来讲，采用的$Dijkstra$不是本身的含义，只是一个协助$DP$的枚举过程。

#### $Code$
```cpp {.line-numbers}
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int N = 100010, M = 2000010;

int n, m;
int dis1[N], dis2[N];

// 正反建图，传入头数组指针
int h1[N], h2[N], e[M], ne[M], w[M], idx;
void add(int *h, int a, int b, int c = 0) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

// 每个节点的价值
int v[N];

void dijkstra1() {
    memset(dis1, 0x3f, sizeof dis1);
    priority_queue<PII, vector<PII>, greater<PII>> q;
    dis1[1] = v[1];
    q.push({dis1[1], 1});

    while (q.size()) {
        int u = q.top().second;
        q.pop();

        for (int i = h1[u]; ~i; i = ne[i]) {
            int j = e[i];
            if (dis1[j] > min(dis1[u], v[j])) {
                dis1[j] = min(dis1[u], v[j]);
                q.push({dis1[j], j});
            }
        }
    }
}

void dijkstra2() {
    memset(dis2, -0x3f, sizeof dis2);
    priority_queue<PII> q;
    dis2[n] = v[n];
    q.push({dis2[n], n});

    while (q.size()) {
        int u = q.top().second;
        q.pop();
        
        for (int i = h2[u]; ~i; i = ne[i]) {
            int j = e[i];
            if (dis2[j] < max(dis2[u], v[j])) {
                dis2[j] = max(dis2[u], v[j]);
                q.push({dis2[j], j});
            }
        }
    }
}

int main() {
    // 正反两张图
    //  Q:为什么要反着建图，用正着的图不行吗？
    //  A:不行啊，因为从n向其它地方走，原来的有向图无法向对面走啊，反着建图就行了
    memset(h1, -1, sizeof h1);
    memset(h2, -1, sizeof h2);

    scanf("%d %d", &n, &m);                          // n个节点，m条边
    for (int i = 1; i <= n; i++) scanf("%d", &v[i]); // 每个节点购买水晶球的金额

    while (m--) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        // 不管是单向边，还是双向边，第一条a->b的边肯定跑不了吧

        if (c == 1) { // 单向边
            // 正向图保存单向边
            add(h1, a, b);
            // 反向图保存单向边
            add(h2, b, a);
            // 注意：这可不是在一个图中创建两条来回的边，而是在两个图中创建两个相反的边。
            // 权值呢？没有，为什么呢？因为我们不关心边权，而是关心此节点中水晶球的价格v[i]，这并不是边权,可以理解为点权
        } else { // 双向边
            // 正向图保存双向边
            add(h1, a, b), add(h1, b, a);
            // 反向图保存双向边
            add(h2, a, b), add(h2, b, a);
        }
    }
    // 正向图跑一遍dijkstra
    dijkstra1();

    // 反向图跑一遍dijkstra
    dijkstra2();

    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = max(dis2[i] - dis1[i], ans);

    printf("%d\n", ans);
    return 0;
}
```

$TODO$
#### [$P2176$ $RoadBlock$ $S$](https://www.luogu.com.cn/problem/P2176)
```cpp {.line-numbers}

```