题解：P3001 [USACO10DEC] Big Macs Around the World G

· · 题解

NOIP 考前复习一下 SPFA 判断负环，刚好今天模拟赛出了一道最短路。

SPFA 的本质就是基于 BFS，通过维护一个队列来遍历所有点并松弛每条边，从而求出最短路。

这道题中就是将松弛操作中的加法改为了乘法，但是随之出现了一个问题，如果存在一个环的每条边都小于 1，那么就会出现类似于普通最短路中的“负环”，这也就是为什么我们需要使用 SPFA 算法。

SPFA 判断负环的方式：在松弛边的时候记录根据到当前点 v 所需经过的点 cnt，如果 cnt\ge n，那么就一定出现了负环，直接输出 0 即可。

代码：

#include<bits/stdc++.h>
using namespace std;

#define ll long long 
#define double long double 
const int N=2.5e5+5;

int n,m,a,b;
double V;

#define pii pair<double,int> 
#define val first 
#define to second 

vector<pii> G[N];

bool vis[N];
double dis[N];
int cnt[N];

void SPFA(int start,int des,double V){
    memset(vis,0,sizeof(vis));
    memset(cnt,0,sizeof(cnt));
    for(int i=1;i<=n;i++) dis[i]=1e18;
    queue<int> q;   

    dis[start]=V,vis[start]=1;
    q.push(start);

    while(!q.empty()){
        int u=q.front(); q.pop();
        vis[u]=0;
        for(auto p:G[u]){
            int v=p.to;
            double w=p.val;
            if(dis[v]>dis[u]*w){
                dis[v]=dis[u]*w,cnt[v]=cnt[u]+1;
                if(cnt[v]>=n) return cout<<0<<"\n",void();
                if(vis[v]==0) vis[v]=1,q.push(v);
            }
        }
    }

    cout<<fixed<<setprecision(10)<<dis[des]<<"\n";
    return;
}

void solve(){
    cin>>n>>m>>V>>a>>b;
    for(int i=1;i<=m;i++){
        int u,v; double w;
        cin>>u>>v>>w;
        G[u].push_back({w,v});
    }
    return SPFA(a,b,V),void();
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int T=1;
    while(T--){
        solve();
    }

    return 0;
}