题目大意：每一个城市都有一定的繁荣度，然后给出m条有向边i->j，定义这条边的权值为pow(arr[j]-arr[i],3)，然后给你q个询问，每个询问输入一个x。
然后问你点1到x的距离，如果小与3或者不可到达，那么输出？，否则的话就输出dis[x]。
题解：如果说这是一个无向图，那么如果这个图内存在负环，那么输出一定是?，因为点y假设可以到打1，那么就可以通过负环无限减小到y的距离，这样的话一定是小于3的。但这是个有向图，该怎么操作呢?我们可以把与负环相连接的元素给他打上标记，另外，如果说点z和负环相连，也就没必要对z进行松弛了...
code:
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll INF=1e18+7; const ll N=1e5+7; struct stu{ ll to,nxt; ll weight; }edge[N]; ll time1=1; ll n; ll cnt=0,head[N]; ll dis[N]; bool mark[N],cir[N]; ll num[N]; ll value[N]; void add(ll x,ll y,ll weight){ edge[cnt].to=y; edge[cnt].weight=weight; edge[cnt].nxt=head[x]; head[x]=cnt++; } void dfs(int v){ cir[v]=1; for(int i=head[v];i!=-1;i=edge[i].nxt){ v=edge[i].to; if(!cir[v]) dfs(v); } } bool spfa(){ for(ll i=0;i<=n;i++) dis[i]=INF; memset(cir,0,sizeof cir); memset(mark,0,sizeof mark); memset(num,0,sizeof num); dis[1]=0; queue<ll>que; que.push(1); num[1]++; mark[1]=1; while(que.size()){ ll u=que.front(); que.pop(); mark[u]=0; for(ll i=head[u];i!=-1;i=edge[i].nxt){ ll v=edge[i].to; if(cir[v]) continue ; if(dis[v]>dis[u]+edge[i].weight){ dis[v]=dis[u]+edge[i].weight; if(!mark[v]) { num[v]++; mark[v]=1; que.push(v); if(num[v]>=n) dfs(v); } } } } return 0; } void solve(){ memset(head,-1,sizeof head); cnt=0; cin>>n; for(ll i=1;i<=n;i++) cin>>value[i]; ll m,x,y; cin>>m; for(ll i=1;i<=m;i++){ cin>>x>>y; add(x,y,(value[y]-value[x])*(value[y]-value[x])*(value[y]-value[x])); } spfa(); ll problem; cin>>problem; ll time=1; printf("Case %d:\n",time1++); while(problem--){ ll q; cin>>q; if(cir[q]||dis[q]<3||dis[q]==INF){ cout<<"?"<<endl; } else{ cout<<dis[q]<<endl; } } } int main(){ ll t; cin>>t; while(t--) solve(); return 0; }
Extended Traffic LightOJ - 1074 （经典SPFA问题）
原文：https://www.cnblogs.com/Accepting/p/12745192.html