本文共 2009 字，大约阅读时间需要 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);
}
      
     
    
   

代码解释

通过SPFA算法，我们能够高效地计算出火车站到各个点的最短路径，并统计满足条件的最短路径数量。

转载地址：http://rqewz.baihongyu.com/