题意：
a到达b城市所需费用为两地人数差的三次方，注意费用可能为负数，求到各个点所需费用。
思路：
因为费用可能为负数，所以可能存在负环。用spfa判断即可。
#include<iostream> #include<cstdio> #include<queue> #include<cstring> using namespace std; const int MAX=0x3f3f3f3f,mx=210; int dis[mx],c[mx],r[mx],vis[mx],h[mx],p[mx],cen[mx]; int n,m,Q; struct{ int u,v,w,next; }shu[41000]; void dfs(int x){ r[x]=1; int i=h[x]; if(!r[shu[i].v]) dfs(shu[i].v); } void spfa(){ memset(dis,0x3f3f3f3f,sizeof(dis)); memset(r,0,sizeof(r)); memset(vis,0,sizeof(vis)); memset(cen,0,sizeof(cen)); queue<int>q; q.push(1); dis[1]=0; while(!q.empty()){ int x=q.front(); q.pop(); vis[x]=0; for(int i=h[x];i!=-1;i=shu[i].next){ int v=shu[i].v; if(r[v]) continue; if(dis[v]>dis[x]+shu[i].w){ dis[v]=dis[x]+shu[i].w; if(!vis[v]){ vis[v]=1; q.push(v); if(++cen[v]>=n) dfs(v); } } } } for(int i=0;i<Q;i++){ int t=c[i]; if(dis[t]==MAX||r[t]||dis[t]<3) puts("?"); else printf("%d\n",dis[t]); } } int main(){ int T,ca=1; scanf("%d",&T); while(T--){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&p[i]); scanf("%d",&m); memset(h,-1,sizeof(h)); for(int i=0;i<m;i++){ int u,v; scanf("%d%d",&u,&v); shu[i].u=u; shu[i].v=v; shu[i].w=(p[v]-p[u])*(p[v]-p[u])*(p[v]-p[u]); shu[i].next=h[u]; h[u]=i; } scanf("%d",&Q); for(int i=0;i<Q;i++) scanf("%d",&c[i]); printf("Case %d:\n",ca++); spfa(); } return 0; }
