Codeforces Round #257 (Div. 1) B. Jzzhu and Cities（多条最短路）
本文共 1951 字，大约阅读时间需要 6 分钟。
SPFA算法是一种用于计算图中单源最短路径的高效方法，特别适用于边权为非负数的图。在本次工程中，我们使用SPFA算法来解决一个与火车站相关的最短路径问题。
代码解析
#include using namespace std;typedef long long ll;const int maxn = 3e5 + 1;int n, m, k, u, v, w, x[maxn], y[maxn], cnt = 0;ll d[maxn], num[maxn];bool vis[maxn];vector > g[maxn << 1);void spfa(int x) { memset(vis, false, sizeof(vis)); for (int i = 0; i <= n; ++i) { d[i] = 1e18; num[i] = 0; } d[x] = 0; num[x] = 1; queue q; q.push(x); vis[x] = true; while (!q.empty()) { int top = q.front(); q.pop(); vis[top] = false; for (auto v : g[top]) { if (d[top] + v.second < d[v.first]) { d[v.first] = d[top] + v.second; num[v.first] = num[top]; if (!vis[v.first]) { q.push(v.first); vis[v.first] = true; } } else if (d[top] + v.second == d[v.first]) { num[v.first]++; } } }}int main() { scanf("%d %d %d", &n, &m, &k); for (int i = 1; i <= k; ++i) { scanf("%d", &u); scanf("%d", &v); scanf("%d", &w); g[u].push_back({v, w}); g[v].push_back({u, w}); scanf("%d", &x[i]); scanf("%d", &y[i]); g[1].push_back({x[i], y[i]}); g[x[i]].push_back({1, y[i]}); } spfa(1); if (d[x[i]] < y[i]) { cnt++; if (d[x[i]] == y[i] && num[x[i]] > 1) { cnt++; num[x[i]]--; } } printf("%d\n", cnt);}
代码解释
数据结构初始化
g是一个邻接表，用于存储图的边信息。d数组用于存储从源点到各个点的最短距离。num数组用于记录到达各点的最短路径的次数。vis数组用于标记当前点是否在队列中。
SPFA算法实现
- 使用双端队列
q进行广度优先搜索。 spfa函数初始化时，所有点的距离设为无穷大，源点距离设为0。- 将源点入队，并标记为已访问。
- 每次从队列中取出点
top，更新其邻接点的距离和计数器。 - 如果发现更短的路径，更新距离和计数器，并将邻接点入队。
- 如果发现与当前最短距离相等的路径，增加计数器。
处理结果
- 遍历所有火车站，比较实际计算的最短距离和预期距离。
- 如果实际距离小于预期距离，计数器
cnt加1。 - 如果实际距离等于预期距离且有多条最短路径，计数器
cnt再加1，并减少计数器以避免重复计数。
通过SPFA算法，我们能够高效地计算出火车站到各个点的最短路径，并统计满足条件的最短路径数量。
转载地址：http://rqewz.baihongyu.com/