感谢：cherish_lin的BLOG。
思路：
POJ 仍然没有修好…单源点，有向图，含负权，最短路。特殊之处在于，需要判断某个点是否在负环内。SPFA，邻接表，标记负环（DFS）。注意，标记负环的流程：
找到一个负环内的点标记它，对它通往的所有点继续搜索并标记。（通往最先找到的点的那个点不能标记）。
代码：
44ms 2332kB
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 205;
int T;
int N,M,Query;
int W[maxn];
int dis[maxn];
int num[maxn];
bool vis[maxn];
bool cir[maxn];
struct EDGE{
int to;
int w;
int fo;
};
EDGE E[maxn * 100];
int tail[maxn];
void ADDEDGE(int i,int u,int v,int w){
E[i].to = v;
E[i].w = w;
E[i].fo = tail[u];
tail[u] = i;
return ;
}
queue<int> Q;
void INIT(){
memset(dis,INF,sizeof(dis));
memset(tail,-1,sizeof(tail));
memset(cir,0,sizeof(cir));
memset(num,0,sizeof(num));
memset(vis,0,sizeof(vis));
return ;
}
void DFS(int id){
cir[id] = true;
for(int i=tail[id] ; ~i ; i=E[i].fo){
if(!cir[E[i].to])
DFS(E[i].to);
}
return ;
}
void SPFA(){
Q.push(1);vis[1]=1;num[1]=1;dis[1]=0;
while(Q.size()){
int cur = Q.front() ; Q.pop(); vis[cur] = false;
if(cir[cur])//已经标记过负环，skip
continue;
for(int i=tail[cur] ; ~i ; i=E[i].fo){
int v = E[i].to ;
if(dis[v] > dis[cur] + E[i].w){
dis[v] = dis[cur] + E[i].w;
if(!vis[v]){
Q.push(v);vis[v]=true;num[v]++;
if(num[v] == N)
DFS(v);
}
}
}
}
return ;
}
int main(){
scanf("%d",&T);
for(int t=1;t<=T;t++){
INIT();
scanf("%d",&N);
for(int i=1;i<=N;i++)
scanf("%d",&W[i]);
scanf("%d",&M);
for(int i=1;i<=M;i++){
int u,v;
scanf("%d%d",&u,&v);
int w = (W[v] - W[u]) ;
ADDEDGE(i,u,v,w*w*w);
}
SPFA();
scanf("%d",&Query);
printf("Case %d:\n",t);
while(Query--){
int k;scanf("%d",&k);
if(cir[k] || dis[k] == INF || dis[k] < 3)
printf("?\n");
else
printf("%d\n",dis[k]);
}
}
return 0;
}
