devbox
繁依Fanyi0
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

单源最短路径

作者：繁依Fanyi0 | 2024-03-15 18:23:58

赞

踩

单源最短路径

单源最短路径

1. 单源最短路径原理

单源最短路径算法分类

在这里插入图片描述

/**
   对应算法(n是顶点数，m是边数)：
    --单源最短路
        --所有边权都是正数
            --朴素Dijkstra算法          O(n^2)                适合于稠密图
            --堆优化版的Dijkstra算法     O(m*log(n))           适合于稀疏图
        --存在负权边
            --Bellman-Ford            O(n*m)                适用于只选择不超过k条边的路径
            --SPFA                    一般是O(m), 最坏O(n*m)  Bellman-Ford的优化
    --多源汇最短路
        -- Floyd算法                  O(n^3)
 */

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

各种算法的原理

  • 朴素版的Dijkstra算法

在这里插入图片描述

  • 堆优化版的Dijkstra算法

    在朴素版的Dijkstra基础上使用小根堆优化，每次可以直接从堆中取出最小值。此时操作(1)、(2)都变成O(1)的了，操作(3)之前相当于将每条边遍历了一次，一共执行m次，优化后在堆中修改一个数的时间复杂度是O(log(n))，因此最终的时间复杂度为：O(m*log(n))

  • Bellman_Ford算法

    可以处理含有负权边的情况，同时还能判断出图中是否有负权回路，但是判断的代价比较大，一般不用该算法判断存在负权回路。我们常用spfa算法判断负权回路。

    在这里插入图片描述

  • spfa算法

    要求图中不能存在负权环，一般99.9%的题目中都不存在负环。spfa相当于对bellman_ford算法进行优化。

在这里插入图片描述

AcWing 849. Dijkstra求最短路 I

问题描述

分析

  • 本题有最多500个点，但是最多有十万条边，因此是稠密图，非常适合使用朴素版的Dijkstra算法来写。
  • 因为图中可能存在重边和自环，并且边权都是非负的，因此求最短路时自环可以忽略，重边选一条权值最小的边即可。

代码

  • C++
#include <iostream>
#include <cstring>

using namespace std;

const int N = 510;

int n, m;
int g[N][N];  // 邻接矩阵
int dist[N];  // 1号点到其他点的距离
bool st[N];  // 记录是否求出了最短路径

int dijkstra() {
    
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    for (int i = 0; i < n; i++) {
        // 选最小值
        int t = -1;
        for (int j = 1; j <= n; j++)
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        // 得到一个解
        st[t] = true;
        // 更新距离
        for (int j = 1; j <= n; j++)
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
    
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main() {
    
    scanf("%d%d", &n, &m);
    
    memset(g, 0x3f, sizeof g);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = min(g[a][b], c);
    }
    
    int t = dijkstra();
    
    printf("%d\n", t);
    
    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

AcWing 850. Dijkstra求最短路 II

问题描述

分析

  • 这一题顶点的数量和边的数量基本在一个数量级，属于稀疏图，适合使用堆优化版的dijkstra算法。

代码

  • C++
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 150010;

int n, m;
int h[N], e[N], w[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++;
}

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();
        
        int ver = t.second, distance = t.first;
        if (st[ver]) continue;
        st[ver] = true;
        
        for (int i = h[ver]; ~i; i = ne[i]) {
            int j = e[i];  // (i, j)这条边的权重为w[i]
            if (dist[j] > distance + w[i]) {
                dist[j] = distance + 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);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    
    int t = dijkstra();
    
    printf("%d\n", t);
    
    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

AcWing 853. 有边数限制的最短路

问题描述

分析

  • bellma_ford算法流程可以参考上面的分析。
  • bellma_ford算法只需要将所有的边存起来即可，不一定需要用邻接表或者邻接矩阵存储。

代码

  • C++
#include <iostream>
#include <cstring>

using namespace std;

const int N = 510, M = 10010;

int n, m, k;
int dist[N], backup[N];  // backup用于防止串联

struct Edge {
    int a, b, w;
} edges[M];

int bellman_ford() {
    
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    for (int i = 0; i < k; i++) {
        memcpy(backup, dist, sizeof dist);
        for (int j = 0; j < m; j++) {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            dist[b] = min(dist[b], backup[a] + w);
        }
    }
    
    // 正无穷可能被更新变小，虽然还是表示正无穷
    // 权值最小为-10000, 最多更新500次, 最多减少五百万
    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    return dist[n];
}

int main() {
    
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < m; i++) {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        edges[i] = {a, b, w};
    }
    
    int t = bellman_ford();
    
    if (t == -1) puts("impossible");
    else printf("%d\n", t);
    
    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

AcWing 851. spfa求最短路

问题描述

分析

  • spfa算法流程可以参考上面的分析。

代码

  • C++
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 100010;

int n, m;
int h[N], e[N], w[N], ne[N], idx;
int dist[N];
bool st[N];  // 表示某个点是否在队列中，保证每个点最多在队列中出现1次

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

int spfa() {
    
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    queue<int> q;
    q.push(1);
    st[1] = true;
    
    while (q.size()) {
        int t = q.front(); q.pop();
        
        st[t] = false;
        
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                if (!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main() {
    
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    
    int t = spfa();
    
    if (t == -1) puts("impossible");
    else printf("%d\n", t);
    
    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

AcWing 852. spfa判断负环

问题描述

分析

在这里插入图片描述

代码

  • C++
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 2010, M = 10010;

int n, m;
int h[N], w[M], e[M], ne[M], idx;
int dist[N], cnt[N];  // cnt[i]表示到虚拟源点的距离-1
bool st[N];

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

bool spfa() {
    
    queue<int> q;
    for (int i = 1; i <= n; i++) {  // 相当于有一个虚拟源点，所有的点都要加入
        q.push(i);
        st[i] = true;
    }
    
    while (q.size()) {
        
        int t = q.front(); q.pop();
        st[t] = false;
        
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return true;
                if (!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    
    return false;
}

int main() {
    
    scanf("%d%d", &n, &m);
    
    memset(h, -1, sizeof h);
    
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    
    if (spfa()) puts("Yes");
    else puts("No");
    
    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

2. 单源最短路的建图方式

AcWing 1129. 热浪

问题描述

分析

  • 题目抽象出来就是要求解从一个点到另外一个点的最短路径。

代码

  • C++
#include <iostream>
#include <cstring>

using namespace std;

const int N = 2510, M = 6200 * 2 + 10;

int n, m, S, T;
int h[N], w[M], e[M], ne[M], idx;
int dist[N], q[N];  // q为手写的循环队列
bool st[N];  // spfa算法中某个点是否已经在队列中

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

int spfa() {
    
    memset(dist, 0x3f, sizeof dist);
    dist[S] = 0;
    
    int hh = 0, tt = 0;
    q[tt++] = S;
    st[S] = true;
    
    while (hh != tt) {
        int t = q[hh++];
        if (hh == N) hh = 0;
        st[t] = false;
        
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                if (!st[j]) {
                    q[tt++] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
    
    return dist[T];
}

int main() {
    
    cin >> n >> m >> S >> T;
    
    memset(h, -1, sizeof h);
    
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    
    cout << spfa() << 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

AcWing 1128. 信使

问题描述

分析

  • 这一题相当于让求解从1号哨所到其他所有哨所的最短距离的最大值，因为n最大为100，完全可以用多源最短路径求解，最多计算10^6次。
  • 这里使用朴素版的dijkstra算法求解。

代码

  • C++
#include <iostream>
#include <cstring>

using namespace std;

const int N = 110;

int n, m;
int g[N][N];
int dist[N];
bool st[N];  // 是否已经求出最短路径

int dijkstra() {
    
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    for (int i = 0; i < n; i++) {
        int t = -1;
        for (int j = 1; j <= n; j++)
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
                
        st[t] = true;
        
        for (int j = 1; j <= n; j++)
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
    
    int res = 0;
    for (int i = 1; i <= n; i++) res = max(res, dist[i]);
    
    if (res == 0x3f3f3f3f) return -1;
    return res;
}

int main() {
    
    cin >> n >> m;
    
    memset(g, 0x3f, sizeof g);
    
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = 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

AcWing 1127. 香甜的黄油

问题描述

分析

  • 分析题目可知这一题相当于：让我们确定一个起点，其他所有点到这个点的最短路径的值最小，输出这个起点。

  • 这相当于让我们求解任意两点之间的最短路径。

  • 这一题顶点数n最大为800，边数m最大为1450，考虑各种算法的时间复杂度（对于前三种算法，都需要再乘一个n）：

    /**
  --朴素Dijkstra算法          O(n^3) = 512,000,000
  --堆优化版的Dijkstra算法     O(n*m*log(n)) = 一千多万
  --SPFA                    O(n*m) = 一百多万
  -- Floyd算法               O(n^3) = 512,000,000
 */

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

    分析可知，这一题可以使用堆优化版的Dijkstra算法或者spfa算法。

代码

  • C++
#include <iostream>
#include <cstring>

using namespace std;

const int N = 810, M = 3000, INF = 0x3f3f3f3f;

int n, p, m;  // n:奶牛数量; p:牧场数量; m:道路数量
int id[N];  // 每头牛所在的牧场编号
int h[N], e[M], w[M], ne[M], idx;
int dist[N], q[N];  // q为循环队列
bool st[N];

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

int spfa(int start) {
    
    memset(dist, 0x3f, sizeof dist);
    dist[start] = 0;
    
    int hh = 0, tt = 1;
    q[0] = start, st[start] = true;
    while (hh != tt) {
        int t = q[hh++];
        if (hh == N) hh = 0;
        
        st[t] = false;
        
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                if (!st[j]) {
                    q[tt++] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
    
    int res = 0;
    for (int i = 0; i < n; i++) {
        int j = id[i];  // 第i头牛所在的牧场编号为j
        if (dist[j] == INF) return INF;
        res += dist[j];
    }
    return res;
}

int main() {
    
    cin >> n >> p >> m;
    for (int i = 0; i < n; i++) cin >> id[i];
    
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    
    int res = INF;
    for (int i = 1; i <= p; i++) res = min(res, spfa(i));
    
    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

AcWing 1126. 最小花费

问题描述

分析

  • 假设转账后剩余的钱的比例为w，则相当于找到一条路径 w 1 , w 2 , . . . , w k w_1,w_2,...,w_k w1​,w2​,...,wk​，使得 A × w 1 × w 2 × . . . × w k = 100 A\times w_1\times w_2\times ... \times w_k=100 A×w1​×w2​×...×wk​=100时A的值最小，相当于 T = w 1 × w 2 × . . . × w k T=w_1\times w_2\times ... \times w_k T=w1​×w2​×...×wk​最大，对T取对数，则有： l o g ( w 1 ) + l o g ( w 2 ) + . . . + l o g ( w k ) log(w_1)+log(w_2)+...+log(w_k) log(w1​)+log(w2​)+...+log(wk​)最大，因为w的值在0~1之间，所以 l o g ( w ) log(w) log(w)是小于0的，因此相当于对 − l o g ( w 1 ) − l o g ( w 2 ) − . . . − l o g ( w k ) -log(w_1)-log(w_2)-...-log(w_k) −log(w1​)−log(w2​)−...−log(wk​)取最小值。问题已经被转换成了最短路径的问题，并且 1 l o g ( w ) ≥ 0 1log(w)\ge 0 1log(w)≥0，可以使用spfa或者dijkstra算法。
  • 这里演示使用dijkstra解决该问题。

代码

  • C++
#include <iostream>
#include <cstring>

using namespace std;

const int N = 2010;

int n, m, S, T;
double g[N][N];  // 默认值为0，表示不连通
double dist[N];
bool st[N];

void dijkstra() {
    
    dist[S] = 1;
    for (int i = 0; i < n; i++) {
        int t = -1;
        for (int j = 1; j <= n; j++)
            if (!st[j] && (t == -1 || dist[j] > dist[t]))
                t = j;
        
        st[t] = true;
        
        for (int j = 1; j <= n; j++)
            dist[j] = max(dist[j], dist[t] * g[t][j]);
    }
}

int main() {
    
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        double z = (100.0 - c) / 100;
        g[a][b] = g[b][a] = z;
    }
    
    scanf("%d%d", &S, &T);
    
    dijkstra();
    
    printf("%.8lf", 100 / dist[T]);
    
    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

AcWing 920. 最优乘车

问题描述

分析

  • 首先考虑如何建图，对于每一条线路，让这条线路上的站点两两建立一条有向边，从前面的站台指向后面的站台，权值为1。
  • 这样原问题就转换成了从1号车站到N号车站的最短路径，使用常规的bfs就可以求解。
  • 一个注意点：题目问的是换车的次数，因此最终的结果为bfs的结果减一，并且不能小于0。

代码

  • C++
#include <iostream>
#include <cstring>
#include <sstream>

using namespace std;

const int N = 510;

int n, m;  // n: 车站数量; m: 路线数量
bool g[N][N];  // 表示从一个站台能否直接到达另一个站台
int dist[N];
int stop[N];  // 读入时存储站台
int q[N];

void bfs() {
    
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    int hh = 0, tt = 0;
    q[0] = 1;
    
    while (hh <= tt) {
        int t = q[hh++];
        
        for (int i = 1; i <= n; i++)
            if (g[t][i] && dist[i] > dist[t] + 1) {
                dist[i] = dist[t] + 1;
                q[++tt] = i;
            }
    }
}

int main() {
    
    cin >> m >> n;

    string line;
    getline(cin, line);  // 读完前面的回车
    while (m--) {
        getline(cin, line);
        stringstream ssin(line);
        int cnt = 0, p;
        while (ssin >> p) stop[cnt++] = p;
        for (int i = 0; i < cnt; i++)
            for (int j = i + 1; j < cnt; j++)
                g[stop[i]][stop[j]] = true;
    }
    
    bfs();
    
    if (dist[n] == 0x3f3f3f3f) puts("NO");
    else cout << max(dist[n] - 1, 0) << 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

AcWing 903. 昂贵的聘礼

问题描述

分析

  • 考虑如何建图，可以考虑使用虚拟源点，以样例为例：

在这里插入图片描述

  • 另外我们还需要考虑等级限制，我们最终要得到1号节点，因此等级一定要包含1号点的等级，我们可以遍历等级区间，做多次dijkstra()算法，相当于滑动窗口。
  • 本题使用朴素版的dijkstra算法求解，顶点数n最多为100，等级最多100个，因此最多运行100次dijkstra算法，一共运行最多一百万次。

代码

  • C++
#include <iostream>
#include <cstring>

using namespace std;

const int N = 110, INF = 0x3f3f3f3f;

int n, m;  // n:物品数量; m:等级限制
int g[N][N], level[N];
int dist[N];
bool st[N];

// 可以交易的等级区间为[down, up]
int dijkstra(int down, int up) {
    
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    
    dist[0] = 0;
    for (int i = 0; i <= n; i++) {  // n + 1个点，循环n+1次
        int t = -1;
        for (int j = 0; j <= n; j++)
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        
        st[t] = true;
        
        for (int j = 0; j <= n; j++)
            if (level[j] >= down && level[j] <= up)
                dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
    
    return dist[1];
}

int main() {
    
    cin >> m >> n;
    
    memset(g, 0x3f, sizeof g);
    
    for (int i = 1; i <= n; i++) {
        int price, cnt;
        cin >> price >> level[i] >> cnt;
        g[0][i] = min(price, g[0][i]);  // 0为虚拟源点
        while (cnt--) {
            int id, cost;
            cin >> id >> cost;
            g[id][i] = min(g[id][i], cost);
        }
    }
    
    int res = INF;
    for (int i = level[1] - m; i <= level[1]; i++)  // 枚举区间左端点
        res = min(res, dijkstra(i, i + m));
    
    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

3. 单源最短路的综合应用

下面四个题中的考点

  • AcWing 1135. 新年好：最短路径+DFS
  • AcWing 340. 通信线路：最短路径+二分
  • AcWing 342. 道路与航线：最短路径+拓扑排序
  • AcWing 341. 最优贸易：最短路径+动态规划

AcWing 1135. 新年好

问题描述

分析

  • 这一题是 最短路径 和 DFS 的结合，我们首先使用优化版的dijkstra算法求出车站1、a、b、c、d、e到其他所有点的单元最短路径；之后从1出发枚举所有可能到达亲戚的顺序，一共有5!中情况，求出最小值即可。

代码

  • C++
#include <iostream>
#include <cstring>
#include <queue>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 50010, M = 200010, INF = 0x3f3f3f3f;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int dist[6][N];
int source[6];  // 起点1、a、b、c、d、e的编号
bool st[N];

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

// 从start开始求单源最短路径，结果存入dist中
void dijkstra(int start, int dist[]) {
    
    memset(st, 0, sizeof st);
    memset(dist, 0x3f, N * 4);
    dist[start] = 0;
    
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, start});  // (距离, 节点编号)
    
    while (heap.size()) {
        auto t = heap.top(); heap.pop();
        
        int ver = t.y, distance = t.x;
        if (st[ver]) continue;
        st[ver] = true;
        
        for (int i = h[ver]; ~i; 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});
            }
        }
    }
}

// u:当前访问的亲戚的个数, 当前的起点是source[0], 当前的距离是distance
int dfs(int u, int start, int distance) {
    
    if (u > 5) return distance;
    
    int res = INF;
    for (int i = 1; i <= 5; i++)
        if (!st[i]) {
            int next = source[i];
            st[i] = true;
            // 当前考察dist[start]这个数组
            res = min(res, dfs(u + 1, i, distance + dist[start][next]));
            st[i] = false;
        }
    return res;
}

int main() {
    
    scanf("%d%d", &n, &m);
    source[0] = 1;
    for (int i = 1; i <= 5; i++) scanf("%d", &source[i]);
    
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }
    
    for (int i = 0; i < 6; i++) dijkstra(source[i], dist[i]);
    
    memset(st, 0, sizeof st);
    printf("%d\n", dfs(1, 0, 0));
    
    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

AcWing 340. 通信线路

问题描述

分析

  • 相当于让我们找到一条线路，这条线路上第k+1大的边是这些可选线路中最小的，输出这条边上的值。

  • 这一题可以使用二分来做，对于区间[0, 1000001]这个区间中的某个点x，定义性质如下：从1走到N，最少经过长度大于x的边的数量是否小于等于K。

  • 假设答案是满足上面性质的最小的一个，记为res，则从1走到N，最少经过长度大于res的边的数量是否小于等于K，且res是最小的一个。对于任意x>=res，因为x变大了，所以上述性质都满足；对于x<res，如果x满足上述性质，则与res是满足性质的最小的一个矛盾。因此根据这个性质可以将区间分为两部分，具有两段性。

  • 这里花费的取值范围是1~1000000，为什么我们要将区间取为[0, 1000001]呢？

    取0是因为路径上的边数小于K，结果可能为0；

    如果区间右端点取为 1 0 6 10^6 106，则如果图中边权全部为 1 0 6 10^6 106，最后结果会返回 1 0 6 10^6 106，如果1号点和N号点不连通，结果也会返回 1 0 6 10^6 106，我们无法区分这两种情况，因此右端点取 1 0 6 10^6 106+1，我们就可以区分这两种情况了。最终结果如果为 1 0 6 10^6 106+1，说明不连通。

代码

  • C++
#include <iostream>
#include <cstring>
#include <deque>

using namespace std;

const int N = 1010, M = 20010;

int n, m, k;
int h[N], e[M], w[M], ne[M], idx;
deque<int> q;
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++;
}

// 从1走到N，经过长度大于bound的边的数量是否小于等于k
// 返回true的话，说明bound还可以再减小
bool check(int bound) {
    
    memset(st, 0, sizeof st);
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    q.push_back(1);
    
    while (q.size()) {
        auto t = q.front(); q.pop_front();
        
        if (st[t]) continue;
        st[t] = true;
        
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i], x = w[i] > bound;
            if (dist[j] > dist[t] + x) {
                dist[j] = dist[t] + x;
                if (!x) q.push_front(j);
                else q.push_back(j);
            }
        }
    }
    
    return dist[n] <= k;
}

int main() {
    
    cin >> n >> m >> k;
    memset(h, -1, sizeof h);
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    
    int l = 0, r = 1e6 + 1;
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    
    if (r == 1e6 + 1) puts("-1");
    else cout << r << 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

AcWing 342. 道路与航线

问题描述

分析

  • 这一题如果使用spfa会被卡。
  • 分析题目可知城镇内部之间的权值是非负的，因此内部可以使用dijkstra算法。对于城镇来说，城镇之间具有拓扑序的关系，因此我们可以按照城镇拓扑序的关系在每个城镇跑Dijkstra算法。
  • 每个城镇称为一个团，但按照拓扑序遍历到某个团时，此时该团中城市的距离不可能再被其他的团更新，因此可以按照拓扑序运行dijkstra算法。
  • 下面几幅图的的参考网址：网址

在这里插入图片描述

  • 算法步骤

在这里插入图片描述

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

在这里插入图片描述

代码

  • C++
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 25010, M = 150010, INF = 0x3f3f3f3f;

int n, mr, mp, S;  // 点数、道路数、航线数、起点
int id[N];  // 顶点所在的团，从1开始
int h[N], e[M], w[M], ne[M], idx;
int dist[N];  // 从S出发的最短路径
int din[N];  // 每个团的入度
vector<int> block[N];  // 每个团包含的顶点
int bcnt;  // 团的个数
bool st[N];  // dijkstra 中的判重数组
queue<int> q;  // 拓扑排序需要的队列

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

void dfs(int u, int bid) {
    
    id[u] = bid, block[bid].push_back(u);
    
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (!id[j])
            dfs(j, bid);
    }
}

void dijkstra(int bid) {
    
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    
    /**
     * 之前的题目只是放入了起点，因为能保证起点是开始的最小(dist==0),但是这道题
     * 里面dijkstra是算每一个团里面的点距离s （最开始那个）的最短路，并不知道这
     * 个团里面的起点是哪一个，所以当然要放全部团里面的点进入优先队列
     */
    for (auto u : block[bid]) heap.push({dist[u], u});
    
    while (heap.size()) {
        
        auto t = heap.top(); heap.pop();
        
        int ver = t.y, distance = t.x;
        if (st[ver]) continue;
        st[ver] = true;
        
        for (int i = h[ver]; ~i; i = ne[i]) {
            int j = e[i];
            if (id[j] != id[ver] && --din[id[j]] == 0) q.push(id[j]);
            if (dist[j] > dist[ver] + w[i]) {
                dist[j] = dist[ver] + w[i];
                if (id[j] == id[ver]) heap.push({dist[j], j});
            }
        }
    }
}

void topsort() {
    
    memset(dist, 0x3f, sizeof dist);
    dist[S] = 0;
    
    for (int i = 1; i <= bcnt; i++)
        if (!din[i])
            q.push(i);
    
    while (q.size()) {
        int t = q.front(); q.pop();
        dijkstra(t);
    }
}

int main() {
    
    scanf("%d%d%d%d", &n, &mr, &mp, &S);
    
    memset(h, -1, sizeof h);
    
    // 读入道路
    while (mr--) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }
    
    // 使用dfs求出每个团, 团的信息存储在id和block中
    for (int i = 1; i <= n; i++)
        if (!id[i])
            dfs(i, ++bcnt);
    
    // 读入航线
    while (mp--) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
        din[id[b]]++;
    }
    
    // 对团之间进行拓扑排序
    topsort();
    
    for (int i = 1; i <= n; i++)
        if (dist[i] > INF / 2) puts("NO PATH");
        else printf("%d\n", dist[i]);
    
    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
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119

AcWing 341. 最优贸易

问题描述

分析

  • 分析如下

在这里插入图片描述

代码

  • C++
#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010, M = 2000010;

int n, m;
int w[N];  // 商品在每个城市的价值
int hs[N], ht[N], e[M], ne[M], idx;  // hs: 正向图; ht: 反向图
int dmin[N], dmax[N];
int q[N];  // 循环队列
bool st[N];  // spfa中的判重数组

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

// h: 邻接表; dist[k]: 1~k号点中买入的最小值
// type: type==0表示求dmin, type==1表示求dmax
void spfa(int h[], int dist[], int type) {
    
    int hh = 0, tt = 1;
    if (type == 0) {
        memset(dist, 0x3f, sizeof dmin);  // dist退化成指针，所以必须用dmin
        dist[1] = w[1];
        q[0] = 1;
    } else {
        memset(dist, -0x3f, sizeof dmax);
        dist[n] = w[n];
        q[0] = n;
    }
    
    while (hh != tt) {
        
        int t = q[hh++];
        if (hh == N) hh = 0;
        
        st[t] = false;
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (type == 0 && dist[j] > min(dist[t], w[j]) || type == 1 && dist[j] < max(dist[t], w[j])) {
                if (type == 0) dist[j] = min(dist[t], w[j]);
                else dist[j] = max(dist[t], w[j]);
                
                if (!st[j]) {
                    q[tt++] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
}

int main() {
    
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
    
    memset(hs, -1, sizeof hs);
    memset(ht, -1, sizeof ht);
    
    while (m--) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(hs, a, b), add(ht, b, a);
        if (c == 2) add(hs, b, a), add(ht, a, b);
    }
    
    spfa(hs, dmin, 0);
    spfa(ht, dmax, 1);
    
    int res = 0;
    for (int i = 1; i <= n; i++) res = max(res, dmax[i] - dmin[i]);
    
    printf("%d\n", res);
    
    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

4. 单源最短路的扩展应用

AcWing 1137. 选择最佳线路

问题描述

分析

  • 这一题和 AcWing 173. 矩阵距离 十分类似，相当于存在多个起点，我们从任意一个起点出发到达终点的最短距离。
  • 一种很显然的做法是从每个起点开始做一遍单源最短路径，所有的结果求一个最小值。这种做法时间复杂度太高，不可取。
  • 还有一种做法是建立反向图，这样从终点开始求一遍单源最短路径即可。然后循环求出到所有起点距离的最小值。
  • 这里不采用上述两种方法，采用建立虚拟源点的方法，即从虚拟源点向所有起点连接一条权值为0的边，这样从虚拟源点做一次单源最短路径即可，如下图：

在这里插入图片描述

代码

  • C++
#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010, M = 21010, INF = 0x3f3f3f3f;

int n, m, T;
int h[N], e[M], w[M], ne[M], idx;
int dist[N], q[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++;
}

int spfa() {
    
    memset(dist, 0x3f, sizeof dist);
    dist[0] = 0;
    
    int hh = 0, tt = 1;
    q[0] = 0;
    while (hh != tt) {
        int t = q[hh++];
        if (hh == N) hh = 0;
        
        st[t] = false;
        
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                if (!st[j]) {
                    q[tt++] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
    
    if (dist[T] == INF) return -1;
    return dist[T];
}

int main() {
    
    while (scanf("%d%d%d", &n, &m, &T) != -1) {
        
        memset(h, -1, sizeof h);
        idx = 0;
        for (int i = 0; i < m; i++) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            add(a, b, c);
        }
        
        int s;
        scanf("%d", &s);
        while (s--) {
            int ver;
            scanf("%d", &ver);
            add(0, ver, 0);  // 0为虚拟源点
        }
        
        spfa();
        
        printf("%d\n", spfa());
    }
    
    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

AcWing 1131. 拯救大兵瑞恩

问题描述

分析

  • 分层图，或者叫做拆点（即可以理解为将一个点拆分为多个点）。
  • 对应于本题，本来(x, y)是一个点，现在将(x, y, state)看成一个点，相当于把一个点拆分成了多个点。
  • 这一题可以采用DP的方式进行分析，DP的求解需要要求状态转移图之间具有拓扑序，不能存在环，但是这里面是可能存在环的，因此最终还是需要转化为图论的方式求解：

在这里插入图片描述

  • 从上图的分析中可以看出：对于1：d[x, y, state] -> d[x, y, state|key]，权值为0；对于2：d[x, y, state] -> d[a, b, state]，权值为1。
  • 我们的终点有 2 P 2^P 2P 个，即d[n, m, 0] ~d[n, m, 2 P − 1 2^P-1 2P−1]（P为门的种类），我们到达其中的任何一种状态即可。
  • 上面的分析就可以把DP问题再次转化成图论问题，因为在该图中只有两种类型的边。所以可以采用双端队列广搜解决，可以参考例题：AcWing 175. 电路维修
  • 这一题的输入比较复杂，我们将每个格子映射为一个整数，左上角的标号为1，右下角的标号为n*m。题目中已经给了墙和门的位置，我们可以使用set记录墙和门的位置，对于互通的其他边，遍历所有的边（采用偏移量技巧），如果不在set中，创建出来。
  • 如果方格是n*n的，则竖边有n*(n-1)，因此一共有2*n*(n-1)，无向边，所以4*n*(n-1)，因为n最大为10，则4*10*9=360条边，因此可以开400条边。

代码

  • C++
#include <iostream>
#include <cstring>
#include <deque>
#include <set>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 11, M = N * N, E = 400, P = 1 << 10;

int n, m, p, k;  // p种门, k迷宫中门和墙的总数
int h[M], e[E], w[E], ne[E], idx;
int g[N][N];  // 二维坐标映射为一维坐标，左上点编号定为1
int key[M];  // 每个位置钥匙的类型
int dist[M][P];  // 到每个点每个状态的最短距离
bool st[M][P];  // 判重数组

set<PII> edges;

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

void build() {
    
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            for (int d = 0; d < 4; d++) {
                int x = i + dx[d], y = j + dy[d];
                if (x <= 0 || x > n || y <= 0 || y > m) continue;
                int a = g[i][j], b = g[x][y];
                if (edges.count({a, b}) == 0) add(a, b, 0);  // 这里约定0可以直接通过
            }
}

int bfs() {
    
    memset(dist, 0x3f, sizeof dist);
    dist[1][0] = 0;  // 编号为1状态为0对应起点，距离起点距离为0
    
    deque<PII> q;
    q.push_back({1, 0});  // (编号, 距离)
    
    while (q.size()) {
        
        auto t = q.front(); q.pop_front();
        
        // cout << t.x << ' ' << t.y << endl;
        // break;
        
        if (st[t.x][t.y]) continue;
        st[t.x][t.y] = true;
        
        if (t.x == n * m) return dist[t.x][t.y];
        
        if (key[t.x]) {  // 当前位置有钥匙，对应边权为0
            int state = t.y | key[t.x];
            if (dist[t.x][state] > dist[t.x][t.y]) {
                dist[t.x][state] = dist[t.x][t.y];
                q.push_front({t.x, state});
            }
        }
        
        for (int i = h[t.x]; ~i; i = ne[i]) {
            int j = e[i];
            if (w[i] && !(t.y >> w[i] - 1 & 1)) continue;  // 有门但是没有对应的钥匙
            if (dist[j][t.y] > dist[t.x][t.y] + 1) {
                dist[j][t.y] = dist[t.x][t.y] + 1;
                q.push_back({j, t.y});
            }
        }
    }
    
    return -1;
}

int main() {
    
    cin >> n >> m >> p >> k;
    
    // 给每个位置一个一维编号
    for (int i = 1, t = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            g[i][j] = t++;
    
    memset(h, -1, sizeof h);
    // 读入墙和门
    while (k--) {
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        int a = g[x1][y1], b = g[x2][y2];
        edges.insert({a, b}), edges.insert({b, a});
        if (c) add(a, b, c), add(b, a, c);
    }
    // 创建可以直接通过的边
    build();
    
    // 读取钥匙的位置
    int s;
    cin >> s;
    while (s--) {
        int x, y, id;
        cin >> x >> y >> id;
        key[g[x][y]] |= 1 << (id - 1);  // id从1开始, 为了节省空间，让编号从0开始
    }
    
    cout << bfs() << 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
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116

AcWing 1134. 最短路计数

问题描述

分析

  • 对于DP我们求解方案数，可以使用一个数组cnt记录方案数，根据状态转移更新cnt，DP类型的问题状态更新必须满足拓扑序。

  • 对于图论求解方案数，我们必须得到一个这样的拓扑图，针对最短路径，我们需要得到最短路树。简单考虑，我们认为边的权值都是大于0 的。

  • 求解单源最短路径的算法可以分为三大类：

    （1）BFS：每次扩展一层，一定可以得到拓扑图。

    （2）Dijkstra（包含双端队列广搜）：每个点第一次出队的时候就确定最小值了，假设当前点u确定最短距离了，u就不可能再更新已经确定最短距离的点了（因为已经确定最短距离的点的距离一定小于u）。

    （3）Bellman_ford（spfa）：不一定满足拓扑序。因为某个点可能入队多次，出队多次，被更新距离的点也是不确定的。

  • 另外再考虑一个问题：如果图中存在负权边，应该怎么办？

    可以使用spfa求出最短路径；然后再把最短路径树建立出来；最后在这个树上统计最短路径次数就可以了

  • 对于本题，因为所有边的权值都为1，使用BFS即可，对于某个点，如果能更新其距离，则更新，并将这个点的条数变成上一点对应的条数；如果说距离相等的话，距离不用更新，条数累加起来即可。

代码

  • C++
#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010, M = 400010, mod = 100003;

int n, m;
int h[N], e[M], ne[M], idx;
int dist[N], cnt[N];  // cnt[i]:1到i的最短路径条数
int q[N];

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

void bfs() {
    
    memset(dist, -1, sizeof dist);
    dist[1] = 0, cnt[1] = 1;
    
    int hh = 0, tt = 0;
    q[0] = 1;
    
    while (hh <= tt) {
        int t = q[hh++];
        
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] == -1) {
                dist[j] = dist[t] + 1;
                cnt[j] = cnt[t];
                q[++tt] = j;
            } else if (dist[j] == dist[t] + 1) {
                cnt[j] = (cnt[j] + cnt[t]) % mod;
            }
        }
    }
}

int main() {
    
    scanf("%d%d", &n, &m);
    
    memset(h, -1, sizeof h);
    
    while (m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }
    
    bfs();
    
    for (int i = 1; i <= n; i++) printf("%d\n", cnt[i]);
    
    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

AcWing 383. 观光

问题描述

分析

  • 这一题需要求出最短路径的条数，以及比最短路径长多恰好多1的路径的条数。
  • 可以使用拆点的方式求解：d[i, 0]表示从1到i的最短路径，d[i, 1]表示从1到i的次短路径。cnt[i, 0]表示从1到i的最短路径条数，cnt[i, 1]表示从1到i的次短路径条数。
  • 对于最短路和次短路按照dijkstra算法来求，都是满足是一个拓扑图，只要权值大于0。
  • 对于每个d[i, 0]和d[i, 1]，我们可以考虑所有指向点i的边，按照边的条数分为若干类，可以先求出每个子集中的最短路和次短路，然后所有这些子集中的最短路和次短路第二小的值就是到该点i的次短路。实际操作的时候，可以只考虑每个点的出边。
  • 最后判断次短路和最短路是不是差为1，如果是的话，结果再加上次短路的条数。

代码

  • C++
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 1010, M = 10010;

struct Ver {
    // id: 节点编号
    // type: 节点类型, 0代表最短路, 1代表次短路
    // dist: 对应最短或者次短距离
    int id, type, dist;
    bool operator> (const Ver &W) const {
        return dist > W.dist;
    }
};

int n, m, S, T;
int h[N], e[M], w[M], ne[M], idx;
int dist[N][2], cnt[N][2];
bool st[N][2];

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

int dijkstra() {
    
    memset(st, 0, sizeof st);
    memset(dist, 0x3f, sizeof dist);
    memset(cnt, 0, sizeof cnt);
    
    dist[S][0] = 0, cnt[S][0] = 1;  // 到S的最短路径为0，路径数目为1条
    priority_queue<Ver, vector<Ver>, greater<Ver>> heap;
    heap.push({S, 0, 0});
    
    while (heap.size()) {
        Ver t = heap.top(); heap.pop();
        
        int ver = t.id, type = t.type, distance = t.dist, count = cnt[ver][type];
        if (st[ver][type]) continue;
        
        st[ver][type] = true;
        
        for (int i = h[ver]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j][0] > distance + w[i]) {  // 可以更新最小值
                dist[j][1] = dist[j][0], cnt[j][1] = cnt[j][0];  // 更新次小值
                heap.push({j, 1, dist[j][1]});
                dist[j][0] = distance + w[i], cnt[j][0] = count;
                heap.push({j, 0, dist[j][0]});
            } else if (dist[j][0] == distance + w[i]) {  // 从t走到j也是最短路径
                cnt[j][0] += count;
            } else if (dist[j][1] > distance + w[i]) {  // 可以更新次小值
                dist[j][1] = distance + w[i], cnt[j][1] = count;
                heap.push({j, 1, dist[j][1]});
            } else if (dist[j][1] == distance + w[i]) {  // 从t走到j也是次短路径
                cnt[j][1] += count;
            }
        }
    }
    
    int res = cnt[T][0];
    if (dist[T][0] + 1 == dist[T][1]) res += cnt[T][1];
    
    return res;
}

int main() {
    
    int cases;
    scanf("%d", &cases);
    while (cases--) {
        scanf("%d%d", &n, &m);
        
        memset(h, -1, sizeof h);
        idx = 0;
        
        while (m--) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            add(a, b, c);
        }
        scanf("%d%d", &S, &T);
        
        printf("%d\n", dijkstra());
    }
    
    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
  • 91

5. 力扣上的单源最短路题目

  • Leetcode 0407 接雨水 II ----> 题目链接 ----> 我的解答：Java、C++ (dijkstra)
  • Leetcode 1514 概率最大的路径 ----> 题目链接 ----> 我的解答：Java、C++ (dijkstra)
  • Leetcode 1631 最小体力消耗路径 ----> 题目链接 ----> 我的解答：Java、C++ (dijkstra)

6. AcWing上的单源最短路题目（其他）

AcWing 592. 雨

问题描述

分析

class Solution {
public:
    int trap(vector<int> &height) {

        int n = height.size();
        if (n == 0) return 0;

        vector<int> left_max(n), right_max(n);

        left_max[0] = height[0];
        for (int i = 1; i < n; i++) left_max[i] = max(left_max[i - 1], height[i]);
        right_max[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) right_max[i] = max(right_max[i + 1], height[i]);

        int res = 0;
        for (int i = 0; i < n; i++) res += min(left_max[i], right_max[i]) - height[i];

        return res;
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 和Leetcode 0042 接雨水的做法类似，我们需要找到从当前位置到达大海的所有路径中的最大值的最小值（从该点到大海有多条路径，每条路径都有一个最大值，我们需要在这些最大值中找到最小的那一个），这个最小值就是下雨后该点的高度。
  • 类似于最短路问题，最短路问题是求解路径总和的最小值；这里的问题是求出所有路径中最大值的最小值。这一题可以采用最短路径的方式求解，下面使用dijkstea算法求解该问题。
  • 本题的起点可以设为大海，相当于新建了一个虚拟源点s。从s向四周的每个格子都连接一条边权为0的边，所有起点不能到达的点标记为正无穷，然后从s求单源最短路径即可（从a走到b的边权定义为b所在位置的高度）。
  • 代码实现时不需要真实地将s建立出来，直接将s到达的所有点加入优先队列即可。
  • 设 d i s t [ i ] [ j ] dist[i][j] dist[i][j]表示从s到 ( i , j ) (i, j) (i,j)所有路径中边权最大值的最小值，如果从 ( i , j ) (i, j) (i,j)能到达 ( x , y ) (x, y) (x,y)，则根据定义一定有： d i s t [ x ] [ y ] ≤ m a x ( d i s t [ i ] [ j ] , h [ x ] [ y ] ) dist[x][y] \le max(dist[i][j], h[x][y]) dist[x][y]≤max(dist[i][j],h[x][y])。解释如下：

在这里插入图片描述

  • 下面还有一个问题，就是要证明一下可以使用dijkstea算法求解该问题。**核心是证明当前从优先队列中出队的元素（假设是 ( x , y ) (x, y) (x,y)）就是最小值，不可能被其他点更新了。**可以用反证法证明，假设当前队首元素会被更新成更小的数据，则一定是被队列中后面的点（假设是 ( i , j ) (i, j) (i,j)）更新，但是从源点到后面的点的值更大，根据 d i s t [ x ] [ y ] dist[x][y] dist[x][y]一定是被 m a x ( d i s t [ i ] [ j ] , h [ x ] [ y ] ) max(dist[i][j], h[x][y]) max(dist[i][j],h[x][y])，这里是取大，所以当前队首元素不可能被更新的更小。

代码

  • C++
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 55;

int n, m;  // 行数、列数
int h[N][N];  // 高度
int dist[N][N];  // dist[i][j]表示到达(i, j)的所有路径中边权最大值的最小值
bool st[N][N];  // 堆优化版的dijkstra算法中判重数组, 为true代表该点已经求出答案
int res;  // 最终存储水的总量

struct Node {
    int x, y, d;  // d: 到达(x, y)的所有路径中边权最大值的最小值
    bool operator< (const Node &t) const {
        return d > t.d;  // 默认大顶堆，需要使用小顶堆
    }
};

void dijkstra() {
    
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    res = 0;
    
    priority_queue<Node> heap;
    
    // 将四周的点加入优先队列
    for (int i = 1; i <= n; i++) {
        heap.push({i, 1, h[i][1]});
        dist[i][1] = h[i][1];
        heap.push({i, m, h[i][m]});
        dist[i][m] = h[i][m];
    }
    for (int i = 2; i < m; i++) {
        heap.push({1, i, h[1][i]});
        dist[1][i] = h[1][i];
        heap.push({n, i, h[n][i]});
        dist[n][i] = h[n][i];
    }
    
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    
    while (heap.size()) {
        
        Node t = heap.top(); heap.pop();
        
        if (st[t.x][t.y]) continue;
        st[t.x][t.y] = true;
        
        res += t.d - h[t.x][t.y];
        
        for (int i = 0; i < 4; i++) {
            int x = t.x + dx[i], y = t.y + dy[i];
            if (x < 1 || x > n || y < 1 || y > m) continue;
            if (dist[x][y] > max(t.d, h[x][y])) {  // (t.x, t.y)到(x, y)的边权为h[x][y]
                dist[x][y] = max(t.d, h[x][y]);
                heap.push({x, y, dist[x][y]});
            }
        }
    }
}

int main() {
    
    int T;
    scanf("%d", &T);
    for (int C = 1; C <= T; C++) {
        
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                scanf("%d", &h[i][j]);
        
        dijkstra();
        
        printf("Case #%d: %d\n", C, res);
    }
    
    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
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/243594
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号