题目链接<http://lightoj.com/volume_showproblem.php?problem=1074>
题意：
一共有N个城市，被M条单向路连接。每个城市都有一个繁忙值，每条路的权值为（终点的繁忙值-起点的繁忙值）^3。一共有Q次的询问操作，问从1号城市到所问城市的最短路是多少。如果权值小于3或路不通，输出'?'。
题解：
题目可能存在负环，要用spfa做，在负环内的城市输出？。
#include <iostream> #include <queue> #include <cstdio> #include <algorithm> #include <string.h> #include <string> using namespace std; typedef long long LL; int busy[205]; int T,n,m,q; struct Edge{ int to,val,next; Edge(int to=0,int val=0,int next=0):to(to),val(val),next(next){} }e[40005]; int len(int u,int v){ return (busy[v]-busy[u])*(busy[v]-busy[u])*(busy[v]-busy[u]); } int head[40005],now; void add(int a,int b){ e[++now]=Edge(b,len(a,b),head[a]),head[a]=now; } int dis[205],vis[205],num[205],cycle[205]; void spfa(){ memset(dis,125,sizeof(dis)); memset(vis,0,sizeof(vis)); memset(num,0,sizeof(num)); memset(cycle,0,sizeof(cycle)); queue<int>q; q.push(1); vis[1]=num[1]=1,dis[1]=0; while(!q.empty()){ int u=q.front(); q.pop(); vis[u]=0; for(int i=head[u];~i;i=e[i].next){ int v=e[i].to; if(cycle[v]) continue; if(dis[v]-dis[u]>e[i].val){ dis[v]=dis[u]+e[i].val; if(!vis[v]){ vis[v]++; num[v]++; q.push(v); } if(num[v]>n) cycle[v]=1; } } } } int main(){ scanf("%d",&T); for(int t=1;t<=T;t++){ memset(head,-1,sizeof(head));now=-1; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&busy[i]); scanf("%d",&m); int a,b; while(m--){ scanf("%d%d",&a,&b); add(a,b); } spfa(); scanf("%d",&q); printf("Case %d:\n",t); while(q--){ scanf("%d",&a); if(dis[a]<3||dis[a]>=(int)1e9||cycle[a]) printf("?\n"); else printf("%d\n",dis[a]); } } } /* 2 5 6 7 8 9 10 6 1 2 2 3 3 4 1 5 5 4 4 5 2 4 5 2 10 10 1 1 2 1 2 */
