题意：
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;
}