题目链接：https://cn.vjudge.net/contest/189021#problem/O
题目大意：有n个站点，每个站点都有一个busyness，从站点A到站点B的花费为（busyness of B - busyness of A）^3。给出个站点间的连通关系（单向），有q次询问，每次询问站点1到x(1<=x<=n)的最小花费，若x点无法到达或者花费小于3则输出‘？’。
解题思路：还是最短路问题，但是图中有负环的存在，所以要判断负环，每次发现负环上的点（qcnt[i]>=n）就用dfs标记该负环上所有的点（负环上的点花费肯定小于3），可以使用spfa来解决。
代码：
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<queue> 5 #include<algorithm> 6 using namespace std; 7 const int N=2e2+5; 8 const int INF=0x3f3f3f3f; 9 10 int n; 11 int dis[N],busy[N],qcnt[N],cost[N][N]; 12 bool vis[N],cir[N]; 13 14 //计算j,k两点间的收费 15 int cal_amt(int j,int i){ 16 return (busy[i]-busy[j])*(busy[i]-busy[j])*(busy[i]-busy[j]); 17 } 18 //标记所有x点能到达的点 19 void dfs(int x){ 20 cir[x]=true; 21 for(int i=1;i<=n;i++){ 22 if(cost[x][i]==1&&!cir[i]) 23 dfs(i); 24 } 25 } 26 27 bool spfa(int s){ 28 memset(dis,0x3f,sizeof(dis)); 29 memset(vis,false,sizeof(vis)); 30 memset(qcnt,0,sizeof(qcnt)); 31 dis[s]=0; 32 queue<int>q; 33 q.push(s); 34 while(!q.empty()){ 35 int k=q.front(); 36 q.pop(); 37 vis[k]=false; 38 for(int i=1;i<=n;i++){ 39 //跳过负环上的点 40 if(i==k||cost[k][i]==-1||cir[i]) 41 continue; 42 if(dis[k]+cal_amt(k,i)<dis[i]){ 43 dis[i]=dis[k]+cal_amt(k,i); 44 if(!vis[i]){ 45 q.push(i); 46 qcnt[i]++; 47 //若存在负环，则dfs标记所有负环上的可达点 48 if(qcnt[i]>=n) 49 dfs(i); 50 vis[i]=true; 51 } 52 } 53 } 54 } 55 } 56 57 int main(){ 58 int t,cas=0; 59 scanf("%d",&t); 60 while(t--){ 61 memset(cost,-1,sizeof(cost)); 62 memset(cir,false,sizeof(cir)); 63 scanf("%d",&n); 64 for(int i=1;i<=n;i++){ 65 scanf("%d",&busy[i]); 66 } 67 int m; 68 scanf("%d",&m); 69 for(int i=1;i<=m;i++){ 70 int a,b; 71 scanf("%d%d",&a,&b); 72 cost[a][b]=1; 73 } 74 int q; 75 scanf("%d",&q); 76 spfa(1); 77 printf("Case %d: ",++cas); 78 for(int i=1;i<=q;i++){ 79 int des; 80 scanf("%d",&des); 81 //若该点在负环上、或者无法到达、或者收费小于3输出'?' 82 if(cir[des]||dis[des]==INF||dis[des]<3) 83 puts("?"); 84 else 85 printf("%d ",dis[des]); 86 } 87 } 88 return 0; 89 }