最短路 | DDOSvoid's Blog

简介

最短路就是最短路

Floyd

本质是一种 $dp$，我们令 $f_{i,j,k}$ 表示从 $i$ 到 $j$ 只经过前 $k$ 个点的最短路径

更新就是枚举中间点 $k$，时间复杂度 $O(n^3)$

一般在写的时候可以直接把第三维压掉

void floyd() { // 注意特判一下 i 以及 j 和 k 相等的情况，避免不必要的更新
    for (int i = 1; i <= n; ++i) f[i][i] = 0;
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j) {
                if (i == j || i == k || j == k) continue;
                f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
            }
}
int main() { 
    fill(f[0], f[0] + maxn * maxn, INF);
}

判负环

Dijkstra

时间复杂度 $O((n+m)\log m)$

不能处理负边权

struct Queue {
    int k; ll d;

    friend bool operator < (const Queue &u, const Queue &v) { return u.d > v.d; } 
}; bool vis[maxn]; ll dis[maxn]; int cnt;
priority_queue<Queue> Q; 
void dijkstra(int s) {
    for (int i = 1; i <= n; ++i) vis[i] = 0;
    for (int i = 1; i <= n; ++i) dis[i] = INF; dis[s] = 0;
    Q.push({ s, 0 });
    while (!Q.empty()) {
        int u = Q.top().k; Q.pop();
        if (vis[u]) continue; vis[u] = 1;
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to, w = e[i].w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                Q.push({ v, dis[v] }); 
            }
        }
    }       
}

SPFA

时间复杂度上限 $O(nm)$，容易被卡

但是可以做负权图

bool vis[maxn]; int dis[maxn];
void spfa() { // SLF
    for (int i = 1; i <= n; ++i) vis[i] = 0;
    for (int i = 1; i <= n; ++i) dis[i] = 0; dis[s] = 0;
    deque<int> Q; Q.push_back(s); 
    while (!Q.empty()) {
        int u = Q.front(); Q.pop_front(); vis[u] = 0;
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to, w = e[i].w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if (vis[v]) continue; vis[v] = 1;
                if (Q.empty() || dis[v] < dis[Q.front()]) Q.push_front(v);
                else Q.push_back(v);
            }
        }
    }
}

bool vis[maxn]; int dis[maxn];
void spfa() { // SLF + 容错
    for (int i = 1; i <= n; ++i) vis[i] = 0;
    for (int i = 1; i <= n; ++i) dis[i] = INF; dis[s] = 0;
    deque<int> Q;Q.push_back(s); 
    while (!Q.empty()) {
        int u = Q.front(); Q.pop_front(); vis[u] = 0;
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to, w = e[i].w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                if (vis[v]) continue; vis[v] = 1;
                if (Q.empty() || dis[v] < dis[Q.front()] + offset) Q.push_front(v);
                else Q.push_back(v);
            }
        }
    }
}

应用

判负环

大概就是一条最短路有多少条边，如果超过 $n - 1$ 条边，说明一定走到负环上了

时间复杂度 $O(nm)$

int dis[maxn], cnt[maxn]; bool vis[maxn];
bool spfa(int s) {
    for (int i = 1; i <= n; ++i) dis[i] = INF; dis[s] = 0; // 其实对于找负环来说 dis[i] 的初始值不重要
    for (int i = 1; i <= n; ++i) cnt[i] = 0;
    for (int i = 1; i <= n; ++i) vis[i] = 0; vis[s] = 1; 
    queue<int> Q; Q.push(s); 
    while (!Q.empty()) {
        int u = Q.front(); Q.pop(); vis[u] = 0; 
        if (cnt[u] >= n) return 1;
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to, w = e[i].w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                cnt[v] = cnt[u] + 1;
                if (vis[v]) continue; vis[v] = 1;
                Q.push(v); 
            }
        }
    } return 0;
}

// 判整张图是否存在负环，方法和上面类似，只需要在一开始将所有点都 push 进队列即可
int dis[maxn], cnt[maxn]; bool vis[maxn];
bool spfa(int s) {
    for (int i = 1; i <= n; ++i) dis[i] = 0;
    for (int i = 1; i <= n; ++i) cnt[i] = 0;
    for (int i = 1; i <= n; ++i) vis[i] = 1;
    queue<int> Q; for (int i = 1; i <= n; ++i) Q.push(i);
    while (!Q.empty()) {
        int u = Q.front(); Q.pop(); vis[u] = 0; 
        if (cnt[u] >= n) return 1;
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to, w = e[i].w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                cnt[v] = cnt[u] + 1;
                if (vis[v]) continue; vis[v] = 1;
                Q.push(v); 
            }
        }
    } return 0;
}

bellman-ford

Johnson 全源最短路

首先我们考虑处理负权边，做法就是建一个超级源 $s$ 连向所有点，边权为 $0$，然后跑一次 $spfa$，求出每个点的距离 $h_i$，然后改造原图，令原图中的边 $(u,v,w)$ 为 $(u,v,w+h_u-h_v)$，然后以每个点为起点跑 $dijkstra$ 即可，时间复杂度 $O(nm\log m)$

#include <iostream>
#include <queue>
#define maxn 3010
#define maxm 6010
#define ll long long
#define INF 1000000000
using namespace std;

int n, m, h[maxn];

struct Edge {
    int fr, to, next, w;
} e[maxm + maxn]; int c1, head[maxn];
inline void add_edge(int u, int v, int w) {
    e[c1].fr = u; e[c1].to = v; e[c1].w = w;
    e[c1].next = head[u]; head[u] = c1++;
}

int dis[maxn]; bool vis[maxn];
bool spfa(int s) {
    queue<int> Q; Q.push(s);
    for (int i = 0; i <= n; ++i) dis[i] = INF; dis[s] = 0;
    for (int i = 0; i <= n; ++i) vis[i] = 0; vis[s] = 1; 
    vector<int> cnt(n + 1);
    while (!Q.empty()) {
        int u = Q.front(); Q.pop(); vis[u] = 0; 
        if (cnt[u] >= n + 1) return 1;
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to, w = e[i].w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                cnt[v] = cnt[u] + 1;
                if (vis[v]) continue; vis[v] = 1;
                Q.push(v);
            }
        }
    } return 0; 
}

struct node {
    int k, d;

    friend bool operator < (const node &u, const node &v) { return u.d > v.d; } 
}; 

void dijkstra(int s) {
    for (int i = 1; i <= n; ++i) dis[i] = INF; dis[s] = 0; 
    for (int i = 1; i <= n; ++i) vis[i] = 0;
    priority_queue<node> Q; Q.push({ s, 0 });
    while (!Q.empty()) {
        int u = Q.top().k; Q.pop();
        if (vis[u]) continue; vis[u] = 1; 
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to, w = e[i].w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                Q.push({ v, dis[v] });
            }
        }
    }
}

int main() { fill(head, head + maxn, -1); 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y, z; cin >> x >> y >> z;
        add_edge(x, y, z); 
    }
    for (int i = 1; i <= n; ++i) add_edge(0, i, 0);
    if (spfa(0)) return cout << -1 << "\n", 0;
    for (int i = 1; i <= n; ++i) h[i] = dis[i];
    for (int i = 0; i < m; ++i) e[i].w += h[e[i].fr] - h[e[i].to];
    for (int i = 1; i <= n; ++i) {
        dijkstra(i); ll ans = 0; 
        for (int j = 1; j <= n; ++j)
            if (dis[j] == INF) ans += 1ll * j * INF;
            else ans += 1ll * j * (dis[j] + h[j] - h[i]);
        cout << ans << "\n";
    }
    return 0;
}

构造最短路

边转点

简要题意：给定一张 $n$ 个点 $m$ 条边的有向图，每条边有两种权值 $a_i,b_i$，对于一条路径，如果路径上的第 $i$ 条边的 $a$ 大于第 $i-1$ 条边的 $a$，那么第 $i$ 条边的权值为 $a-b$，否则为 $a$，求 $1$ 到其它所有点的最短路

$n\le 10^5,m\le 2\times 10^5$

简要题解：注意到一条边的权值跟它上一条边有关系，我们考虑将边转换成点，然后对于原图中的一个中转点，我们考虑将其出边全部新建一个副本，副本与自身相连，然后排序一下串起来即可

考场上的写法有点冗余，点数为 $n+2m+1$，边数为 $6m$，另外需要注意一条边代表它指向的那个点

时间复杂度 $O(6m\log m)$

2021 CCPC网络赛 I Public Transport System

几种特殊的最短路

关键点最短路

考虑这样一个情况，图上任意两个之间的最短路一定经过某些关键点

这样我们可以预处理出这些关键点到其他所有点的单源最短路径

这样在处理多源最短路径的时候可以直接枚举关键点
1. 简要题意：给定一个 $n\times m$ 的四连通网格图，现在有 $k$ 个点不能走，另外还有 $q$ 次询问，每次询问给定起点 $(sx,sy)$ 和中终点 $(tx,ty)$，求起点到终点的最短路
  
  $n\times m \le 2\times 10^5,k\le 42,q\le 10^5$
  
  简要题解：我们考虑如果两个点之间有不能走的点，那么一定存在最短路是沿着不能走的点的
  
  注意到 $k$ 很小，所以我们把 $k$ 周围的点都拿出来然后做多源 $bfs$
  
  最后枚举最短路是经过的那个点即可，时间复杂度 $O(knm+kq)$
  
  2020 China Collegiate Programming Contest, Weihai Site B.Labyrinth
2. 简要题意：给定一个 $n$ 个点 $m$ 条边的无向连通图，边有权，有 $q$ 次询问，每次询问给定一个起点 $s_i$ 和一个终点 $t_i$，求起点到终点的最短路
  
  $n,m,q\le 10^5,m-n\le 20$
  
  简要题解：这张图可以转换为一棵树多连了 $20$ 条边，那么我们可以将 $s_i$ 到 $t_i$ 的最短路分成两种，第一种是只走树边，第二种是要经过一些多余的边
  
  所以我们将这 $20$ 条边所连的 $40$ 个点，看成关键点，对于每个关键点都跑一个最短路即可
  
  注意到关键点只有 $40$ 个，所以我们对于每个关键点跑一遍最短路即可，时间复杂度为 $O(40n\log n)$
  
  CF 1051F The Shortest Statement
3. 简要题意：给定⼀个 $n$ 个点， $m$ 条边的带权⽆向图，其中有 $s$ 个点是加油站。每辆车都有⼀个油量上限 $b$ ，即每次⾏⾛距离不能超过 $b$ ，但在加油站可以补满。 $q$ 次询问，每次给出 $x$，$y$，$b$ ，表示出发点是 $x$ ，终点是 $y$ ，油量上限为 $b$ ，且保证 $x$ 点和 $y$ 点都是加油站，请回答能否从 $x$ ⾛到 $y$
  
  $n,m,q\le 2\times 10^5$
  
  简要题解：我们考虑用将所关键点都扔进 $dijkstra$ 的优先队列里，然后求出离每个非关键点最近的关键点
  
  然后将连接两个属于不同关键点的非关键的边拿出来跑 $kruskal$ 即可
  
  bzoj 4144 [AMPPZ2014]Petrol
将二维平面连通
1. 给定一个二维平面 $nm$ 和 $k$ 个矩形，每个矩形都有一个代价
  
  要求选择代价最小的若干个矩形使得 $(1,1)$ 和 $(n,m)$ 不连通，注意矩形之间可能相交或者重叠
  
  $n,m,k\le 2000$
  
  简要题解：我们以左和下边界为起点，右和上边界为终点，对于每个矩形都建一个点
  
  如果两个矩形相邻或相交，则这两个点相连，然后求最短路即可
  
  校内赛 2021-2-15 Problem G
2. 简要题意：给定一个四连通网格图，其中有一些点是障碍，需要添加最小的障碍使得不存在一条从第一行出发到达最后一行的路径，需要保证任意两个障碍不相邻
  
  $n\times m\le 2\times 10^5$
  
  简要题解：容易发现相当于找一条从第一列到最后一列只走障碍点，且连通性为八连通减掉四连通的最短路
  
  对于障碍点不能四连通相邻的限制我们只需要将与障碍点四连通的点视为不可走的点，障碍点视为 $0$ 边，非障碍点视为 $1$ 边，跑 $01~bfs$ 即可，时间复杂度 $O(n\times m)$
  
  CF 1749E Cactus Wall
特殊限制最短路

一般有两种做法，第一种是拆点拆边，第二种是魔改 $dijkstra$
1. 简要题意：给定一个 $n$ 个点 $m$ 条边的带权无向图，你每次必须连续走两条边，新的边权为 $(w_1+w_2)^2$，求 $1$ 到其它所有点的最短路
  
  $n\le 10^5,m\le 2\times 10^5,w_i\le 50$
  
  简要题解：注意到边权很小，我们考虑对于每个边权都拆点
  
  我们对于一个点拆成 $51$ 个，其中一个代表原始点，另外 $50$ 个代表到这个点且边权为 $w$
  
  对于原图一条边 $(u,v,w)$，我们首先将 $u$ 连 $(v,w)$，边权为 $0$
  
  然后将 $(u,i)$ 连 $v$，边权为 $(i+w)^2$，其中 $i\in [1,50]$
  
  然后我们跑 $dijkstra$ 即可，时间复杂度 $O(50m\log (50m))$
  
  CF 1486E Paired Payment 我们通过新建点来实现题目要求的最短路
2. 简要题意：给定一个 $n$ 个点 $m$ 条边的无向图，有一些点被其它点所保护，对于点 $i$，其保护点为 $l_i$，只有你到达过 $l_i$ 之后才能到 $i$，保证 $l_1=0$，求点 $1$ 到点 $n$ 的最短路
  
  简要题解：注意到我们每次只能拿已经破坏掉结界的点去松弛其他点
  
  所以这东西本质上还是一个 $dijkstra$，只不过只有当一个点的结界被破坏掉才能入队
  
  我们令 $d1[u]$ 表示到达点 $u$ 时间，$d2[u]$ 表示点 $u$ 的结界被破坏掉的时间
  
  Luogu P2446 [SDOI2010]大陆争霸
3. luogu U39019 迷宫 $dis[v]$ 由第 $d+1$ 小的 $dis[u]+w$ 转移
4. 简要题意：给定一个 $n$ 个点 $m$ 条边的无向带权图，图中有两种边，一种是普通边，一种是特殊边，在经过一次特殊边后到达点 $u$，对于与 $u$ 直接相连的点 $v$，其边权从 $w$ 变为 $w-k$，$k$ 是一开始就给定的一个常数，而与 $u$ 不直接相连的点 $v$，可以花费 $0$ 直接到达，求点 $1$ 到其它所有点的最短路
  
  $n,m\le 10^6,w,k\le 10^9$
  
  简要题解：首先拆点，将 $u$ 拆成 $(u,0)$ 和 $(u,1)$，表示是否经过了特殊边到达 $u$
  
  考虑 $dijkstra$ 的过程，每当经过一次特殊边后，我们会拿 $dis_{u,1}$ 去更新所有与 $u$ 不直接相连的点 $v$ 的 $dis_{v,0}$，注意到 $dis_{u,1}$ 在 $dijkstra$ 的过程是递增的，也就说通过这种特殊边的更新，每个 $dis_{v,0}$ 只会有一次
  
  所以我们拿一个 $vector$ 存储所有还没有被特殊边更新过的 $v$，然后对于每个 $u$，我们直接暴力 $vector$ 去更新所有与其不直接相连的 $v$，并将其删除，时间复杂度 $O(n\log m)$
  
  2022杭电多校1 H Path
5. 简要题意：给定一个 $n$ 个点 $m$ 条边的无向图，边权均为 $a$，现在将原图中所有最短路为 $2a$ 的点对 $(i,j)$ 之间加一条长度为 $b$ 的无向边，求新图的以 $S$ 为起点的单源最短路径
  
  $n,m\le 10^5$
  
  注意到只有三元环是没法享受到 $b$ 的路径，而三元环只有 $O(m\sqrt m)$ 个，所以我们直接在 $dijkstra$ 的过程中对于每个中转点维护现在还没有被更新的点集，初始时这个就是与这个点相邻的点，每次会留下与 $(u,v)$ 组成三元环的 $w$，这一部分的更新总时间复杂度就是 $O(m\sqrt m)$
  
  总时间复杂度 $O(m\sqrt m+m\log m)$
  
  Luogu P3547 [POI2013]CEN-Price List