python/TangDou/Topic/【最短路径】Dijkstra算法专题.md

Dijkstra算法专题

一、解决的问题

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

二、算法原理

视频讲解 : 【5分钟搞定Dijkstra算法】

三、题单

【模板题】AcWing 850. Dijkstra求最短路 II

输入样例

3 3
1 2 2
2 3 1
1 3 4

输出样例

3

Code

#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. 热浪

与模板相比，只是起点和终点是输入的，其它无区别。

输入样例：

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

输出样例：

7

Code

#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. 信使

总结：从1号哨所出发，计算出到每个哨所的最短路径，所以最短路径中最长的，表示需要的最少时间，是一个最短路径模板+思维问题。

输入样例：

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

输出样例：

11

Code

#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. 香甜的黄油

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

输入样例：

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

输出样例：

8

Code

#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. 最小花费

假设初始金钱为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\%)的最大值。

输入样例：

3 3
1 2 1
2 3 2
1 3 3
1 3

输出样例：

103.07153164

Code

#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. 最优乘车

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

#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. 昂贵的聘礼

建图方式

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

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

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

等级限制

• 酋长的女儿肯定是要娶到手的，所有的路径都会汇集在 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 号点肯定在区间内。

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

#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. 新年好

一、题目描述

重庆城里有 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

输入样例：

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

输出样例：

21

1. 梳理概念

车站: 1,2,3,4,5,6,7,...,50000，最多可能50000个 这个数量挺大

亲戚个数：5个，分别住 a,b,c,d,e号车站 这个数量挺小，看来可以利用一下

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

2、思考过程

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

至此，整体思路完成。

3.编码步骤

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

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

4.实现细节

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

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

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

\large Code

#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. 通信线路

一、题目描述

在郊区有 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

输入样例：

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

输出样例：

4

二、题目解析

理解题意

找一条路径，边权最大的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

#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 道路与航线

一、题目描述

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

他想把牛奶送到 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。

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

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

他想找到从发送中心城镇 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算法不能解决带有负权边的图，这是为什么呢？下面用一个例子讲解一下

以这里图为例，一共有五个点，也就说要循环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 算法

算法步骤

扩展：用拓扑排序解决dag带负权图的最短路问题

Code

#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. 最优贸易

一、题目描述

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

输入样例：

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

输出样例：

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值是记录 点权的最值 ，在某些情况下是 具有后效性的，如下图：

点权 用绿色数字标示在点号下方，可以发现在点2处会经过一个回路再次回到点2，但在这之前点5的dis已经被更新为3了

解释：因为1 \rightarrow 2 \rightarrow 5这条路线上，在点2时，水晶球的价格最便宜，价格是3

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

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

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

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

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

Code

#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