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

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

news 来源：原创 2025/5/16 17:24:30

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;
}

相关文章：