分析：一看就是求最短路，然后用dij，果断错了一发，发现是3次方，有可能会出现负环
然后用spfa判负环，然后标记负环所有可达的点，被标记的点答案都是“？”
#include<cstdio> #include<cstring> #include<queue> #include<cstdlib> #include<algorithm> #include<vector> #include<cmath> using namespace std; typedef long long LL; const int N=200+5; const int INF=0x7fffffff; struct Edge{ int v; LL w; int next; bool operator<(const Edge &e)const{ return w>e.w; } }edge[N*N]; int head[N],val[N],tot,n,m,p; LL d[N]; void add(int u,int v,LL w){ edge[tot].v=v; edge[tot].w=w; edge[tot].next=head[u]; head[u]=tot++; } bool inq[N]; queue<int>q; int cnt[N]; bool c[N]; void dfs(int u){ c[u]=1; for(int i=head[u];~i;i=edge[i].next) if(!c[edge[i].v])dfs(edge[i].v); } void spfa(int s){ for(int i=1;i<=n;++i) c[i]=cnt[i]=inq[i]=0,d[i]=INF; q.push(s),cnt[s]=1,inq[s]=1,d[s]=0; while(!q.empty()){ int u=q.front(); q.pop(); inq[u]=0; if(c[u])continue; for(int i=head[u];~i;i=edge[i].next){ int v=edge[i].v; if(c[v])continue; if(d[v]>d[u]+edge[i].w){ d[v]=d[u]+edge[i].w; if(inq[v])continue; q.push(v); ++cnt[v]; inq[v]=1; if(cnt[v]>n)dfs(v); } } } } int main(){ int T,cas=0; scanf("%d",&T); while(T--){ scanf("%d",&n); for(int i=1;i<=n;++i)scanf("%d",&val[i]); scanf("%d",&m); memset(head,-1,sizeof(head)),tot=0; for(int i=0;i<m;++i){ int u,v; scanf("%d%d",&u,&v); LL w=(val[v]-val[u]); w=w*w*w; add(u,v,w); } spfa(1); scanf("%d",&p); printf("Case %d: ",++cas); for(int i=1;i<=p;++i){ int u; scanf("%d",&u); if(c[u]||d[u]==INF||d[u]<3)printf("? "); else printf("%d ",d[u]); } } return 0; }