本文共 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);}
      
     
    
   

代码解释

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

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