当前位置：首页 > article >正文

图论——单源最短路的扩展应用

article 2025/1/30 3:11:04

acwing1137.选择最佳路线

本题有两个解决思路
1.建立虚拟源点，连接虚拟源点和 $w$ 个可作为起点的点，边权为0，这样只需要从虚拟源点开始做一遍最短路算法便可。
2.反向建边，把所有的add(a,b,c)变成add(b,a,c)，这样只需要以终点车站作为起点做一遍最短路算法便可。
其中第一种做法的可扩展性更好，可以解决起点和终点多对多的情况，下面采用第一种做法。

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010, M = 21010;
int h[N], e[M], ne[M], w[M];
int tot;
int dist[N];
bool st[N];
int q[N];
int n, m, s;
void add(int a, int b, int c)
{
    e[tot] = b, ne[tot] = h[a], w[tot] = c, h[a] = tot ++ ;
}
int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    dist[0] = 0;
    int hh = 0, tt = 1;
    q[0] = 0;
    while (hh != tt)
    {
        int t = q[hh ++ ];
        st[t] = 0;
        if (hh == N) hh = 0;
        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]) continue;
                q[tt ++ ] = j;
                if (tt == N) tt = 0;
                st[j] = 1;
            }
        }
    }
    if (dist[s] == 0x3f3f3f3f) return -1;
    return dist[s];
}
int main()
{
    while (cin >> n >> m >> s)
    {
        memset(h, -1, sizeof h);
        tot = 0;
        while (m -- )
        {
            int a, b, c;
            cin >> a >> b >> c;
            add(a, b, c);
        }
        int cnt;
        cin >> cnt;
        while (cnt -- )
        {
            int a;
            cin >> a;
            add (0, a, 0);
        }
        int t = spfa();
        cout << t << endl;
    }
    return 0;
}

进行状态压缩，用一个二进制数state表示走到某一个格子时携带的钥匙的情况。
进行状态定义， $d i s t [x] [y] [s t a t e]$ 表示走到格子 $(x, y)$ 时并且状态为state时的最短路长度。
考虑如何建图，如果格子 $(x, y)$ 存在钥匙，那么认为 $d i s t [x] [y] [s t a t e]$ 到 $d i s t [x] [y] [s t a t e ∣ k ey [x] [y]]$ 存在一条长度为0的边； $d i s t [x] [y] [s t a t e]$ 到上下左右可以走到的点 $d i s t [a] [b] [s t a t e]$ 存在一条长度为1的边。因为边权只有0和1，所以可以使用双端队列来做。

#include <iostream>
#include <cstring>
#include <queue>
#include <set>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
const int C = 15, N = 110, M = 410, P = 11;
int h[N], e[M], ne[M], w[M], tot = 0;
int dist[N][1 << P];
int g[C][C];
int key[N];
int st[N][1 << P];
int n, m, p, k;
set<PII> edges;
void add(int a, int b, int c)
{
    e[tot] = b, ne[tot] = h[a], w[tot] = c, h[a] = tot ++ ;
}
void build()
{
    int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            for (int u = 0; u < 4; u ++ )
            {
                int x = i + dx[u], y = j + dy[u];
                if (!x || x == n + 1 || !y || y == m + 1) continue;
                int a = g[i][j], b = g[x][y];
                if (!edges.count({a, b})) add(a, b, 0);
            }
}
int bfs()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1][0] = 0;
    deque<PII> q;
    q.push_back({1, 0});
    while (q.size())
    {
        auto t = q.front();
        q.pop_front();
        int node = t.first, state = t.second;
        if (node == n * m) return dist[node][state];

        if (key[node])
        {
            int state2 = state | key[node];
            if (dist[node][state2] > dist[node][state])
            {
                dist[node][state2] = dist[node][state];
                q.push_front({node, state2});
            }
        }
        for (int i = h[node]; ~i; i = ne[i])
        {
            int j = e[i];
            if (w[i] && !(state >> (w[i] - 1) & 1)) continue;
            if (dist[j][state] > dist[node][state] + 1)
            {
                dist[j][state] = dist[node][state] + 1;
                q.push_back({j, state});
            }
        }
    }
    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, val;
        cin >> x1 >> y1 >> x2 >> y2 >> val;
        int a = g[x1][y1], b = g[x2][y2];
        edges.insert({a, b}), edges.insert({b, a});
        if (val) add(a, b, val), add(b, a, val);
    }
    build();
    int s;
    cin >> s;
    while (s -- )
    {
        int x, y, val;
        cin >> x >> y >> val;
        int a = g[x][y];
        key[a] += 1 << (val - 1);
    }
    cout << bfs();
    return 0;
}

acwing1134.最短路计数

要求最短路计数首先满足条件是不能存在值为0的环，因为存在的话那么被更新的点的条数就为INF了。
要把图抽象成一种最短路树（拓扑图）。
求最短的算法有以下几种
BFS: 只入队一次，出队一次。可以抽象成拓扑图，因为它可以保证被更新的点的父节点一定已经是最短距离了，并且这个点的条数已经被完全更新过了。
dijkstra(包括堆优化版，还有双端BFS): 每个点只出队一次。也可以抽象成拓扑图，同理由于每一个出队的点一定已经是最短距离，并且它出队的时候是队列中距离最小的点，这就代表他的最短距离条数已经被完全更新了，所以构成拓扑性质。
bellman_ford(包括SPFA): 本身不具备拓扑序，因为更新它的点不一定是最短距离，所以会出错。但如果图中存在负权边只能用该算法做，也能做但是比较麻烦,先跑一遍spfa找到每个点的最短距离,把最短路拓扑树建立出来，看哪一条边dist[j] == dist[t] + w[i],然后更新它。

本题的边权只有1，所以可以使用bfs来做。

#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010, M = 2 * 200010, mod = 100003;
int h[N], e[M], ne[M], tot = 0;
int dist[N], cnt[N];
int q[N];
int n, m;
void add(int a, int b)
{
    e[tot] = b, ne[tot] = h[a], h[a] = tot ++ ;
}
void bfs()
{
    memset(dist, 0x3f, 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] > dist[t] + 1)
            {
                dist[j] = dist[t] + 1;
                q[++ tt] = j;
                cnt[j] = cnt[t];
            }
            else if (dist[j] == dist[t] + 1)
            {
                cnt[j] = (cnt[j] + cnt[t]) % mod;
            }
        }
    }
    for (int i = 1; i <= n; i ++ )
        if (dist[i] == 0x3f3f3f3f) cout << 0 << endl;
        else cout << cnt[i] << endl;
    return ;
}
int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    bfs();
    return 0;
}

acwing383.观光

设状态 $d i s t [i] [0]$ 表示从起点到i点的最短路径， $d i s t [i] [1]$ 表示从起点到i点的次短路径。
1. $d i s t [j] [0] > d i s t [v] [t y p e] + w [i]$ :当前最短路变成次短路，更新最短路，将最短路和次短路都加入优先队列。
2. $d i s t [j] [0] = d i s t [v] [t y p e] + w [i]$ :找到一条新的最短路，更新最短路条数。
3. $d i s t [j] [1] > d i s t [v] [t y p e] + w [i]$ :更新次短路，将次短路加入优先队列。
4. $d i s t [j] [1] = d i s t [v] [t y p e] + w [i]$ :找到一条新的次短路，更新最次短路跳条数。

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1010, M = 10010;
int h[N], e[M], ne[M], w[M], tot = 0;
int dist[N][2];
bool st[N][2];
int cnt[N][2];
int t;
int S, T;
struct Node{
    int ver, type, dist;
    bool operator > (const Node& node) const{
        return dist > node.dist;
    }
};
void add(int a, int b, int c)
{
    e[tot] = b, ne[tot] = h[a], w[tot] = c, h[a] = tot ++ ;
}
int dijkstra()
{
    memset(st, 0, sizeof st);
    memset(dist, 0x3f, sizeof dist);
    dist[S][0] = 0;
    cnt[S][0] = 1;
    priority_queue<Node, vector<Node>, greater<Node>> heap;
    heap.push({S, 0, 0});
    while (heap.size())
    {
        Node t = heap.top();
        int ver = t.ver, type = t.type, count = cnt[ver][type];
        heap.pop();
        if (st[ver][type]) continue;
        st[ver][type] = 1;
        for (int i = h[ver]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j][0] > dist[ver][type] + w[i])
            {
                dist[j][1] = dist[j][0];
                cnt[j][1] = cnt[j][0];
                heap.push({j, 1, dist[j][1]});
                dist[j][0] = dist[ver][type] + w[i];
                cnt[j][0] = count;
                heap.push({j, 0, dist[j][0]});
            }
            else if (dist[j][0] == dist[ver][type] + w[i])
                cnt[j][0] += count;
            else if (dist[j][1] > dist[ver][type] + w[i])
            {
                dist[j][1] = dist[ver][type] + w[i];
                cnt[j][1] = count;
                heap.push({j, 1, dist[j][1]});
            }
            else if (dist[j][1] == dist[ver][type] + w[i])
                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()
{
    cin >> t;
    while (t -- )
    {
        int n, m;
        cin >> n >> m;
        memset(h, -1, sizeof h);
        tot = 0;
        while (m -- )
        {
            int a, b, c;
            cin >> a >> b >> c;
            add(a, b, c);
        }
        cin >> S >> T;
        int t = dijkstra();
        cout << t << endl;
    }
    return 0;
}