Extended Traffic SPFA判负环

Extended Traffic

解法：

因为存在负环，则需要使用SPFA求最短路，跑一遍模板，记录负环所能达到的点集

学习博客

#include<bits/stdc++.h> 
using namespace std;
int n,m,q;
int a[202];
struct node
{int v,w;
};
vector<node > G[202];
int inq[202];//当前是否在队列 
int num[202];//进入队列次数  当进入队列次数大于n-1次则存在负环 
int d[202];//最短路 
int cir[202];//负环能达到的点集 void dfs(int u)
{cir[u]=1;for(auto T:G[u]){if(!cir[T.v]) dfs(T.v);}
}
void spfa(int u)
{queue<int> q;memset(inq,0,sizeof(inq));memset(num,0,sizeof(num));memset(cir,0,sizeof(cir));for(int i=1;i<=n;i++) d[i]=1e9;d[u]=0;q.push(u);inq[u]=1;num[u]++;while(q.size()){int v=q.front();q.pop();inq[v]=0;for(auto T:G[v]){if(cir[T.v]) continue;if(d[T.v]>d[v]+T.w){d[T.v]=d[v]+T.w;if(inq[T.v]==0){inq[T.v]=1;q.push(T.v);num[T.v]++;if(num[T.v]>n) dfs(T.v);}}}}}
int main()
{int t;scanf("%d",&t);int tt=1;while(t--){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);G[i].clear();}scanf("%d",&m);for(int i=0;i<m;i++){int u,v;scanf("%d%d",&u,&v);G[u].push_back({v,(a[v]-a[u])*(a[v]-a[u])*(a[v]-a[u])});}spfa(1);int q;scanf("%d",&q);printf("Case %d:\n",tt++);while(q--){int w;scanf("%d",&w);if(cir[w]||d[w]<3||d[w]==1e9) puts("?");else printf("%d\n",d[w]);}}
}