https://vjudge.net/problem/LightOJ-1074
题意：n个节点，给出每个节点的权值，m条单向边u、v，边权为（val[v] - val[u]^3.
q个询问，回答1节点到x节点的最小值。如果不能到达或值小于3，则输出'?'.
解法：spfa+dfs：判负环且需要将负环节点的联通块节点都找到。
//#include<bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <string>
#include <stdio.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string.h>
#include <vector>
#include <stdlib.h>
using namespace std;
typedef long long ll ;
#define int ll
#define mod 100
#define gcd(m,n) __gcd(m, n)
#define rep(i , j , n) for(int i = j ; i <= n ; i++)
#define red(i , n , j) for(int i = n ; i >= j ; i--)
#define ME(x , y) memset(x , y , sizeof(x))
//int lcm(int a , int b){return a*b/gcd(a,b);}
//ll quickpow(ll a , ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;b>>=1,a=a*a%mod;}return ans;}
//int euler1(int x){int ans=x;for(int i=2;i*i<=x;i++)if(x%i==0){ans-=ans/i;while(x%i==0)x/=i;}if(x>1)ans-=ans/x;return ans;}
//const int N = 1e7+9; int vis[n],prime[n],phi[N];int euler2(int n){ME(vis,true);int len=1;rep(i,2,n){if(vis[i]){prime[len++]=i,phi[i]=i-1;}for(int j=1;j<len&&prime[j]*i<=n;j++){vis[i*prime[j]]=0;if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}else{phi[i*prime[j]]=phi[i]*phi[prime[j]];}}}return len}
#define INF 0x3f3f3f3f
#define PI acos(-1)
#define pii pair<int,int>
#define fi first
#define se second
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define size(v) (int)(v.size())
#define cin(x) scanf("%lld" , &x);
const int N = 1e5+9;
const int maxn = 1e3+9;
const double esp = 1e-6;
int val[maxn] , head[maxn] , tol , vis[maxn] , dis[maxn] , ans[maxn];
int cnt , n , x[maxn];
int f[maxn];
struct node{
int v , w , next;
}g[N];
void add(int u , int v , int w){
g[++tol] = {v , w , head[u]};
head[u] = tol;
}
void dfs(int u){
f[u] = 1 ;
for(int i = head[u] ; i ; i = g[i].next){
if(!f[g[i].v]){
dfs(g[i].v);
}
}
}
void spfa(int u){
ME(vis , 0);
fill(dis , dis+maxn , INF);
dis[u] = 0 ; vis[u] = 1 ;
ans[u]++;
queue<int>q;
q.push(u);
while(!q.empty()){
int a = q.front() ; q.pop();
vis[a] = 0 ;
for(int i = head[a] ; i ; i = g[i].next){
int v = g[i].v;
if(f[v])continue;
int w = g[i].w;
if(dis[a] + w < dis[v]){
dis[v] = dis[a] + w ;
if(!vis[v]){
vis[v] = 1 ;
q.push(v);
ans[v]++;
if(ans[v] > n){
dfs(v);
}
}
}
}
}
}
void init(){
ME(head , 0);
ME(ans , 0);
ME(f , 0);
tol = 0;
}
void solve(){
init();
scanf("%lld" , &n);
rep(i , 1 , n){
scanf("%lld" , &val[i]);
}
int m ;
scanf("%lld" , &m);
rep(i , 1 , m){
int u , v ;
scanf("%lld%lld" , &u , &v);
add(u , v , (val[v]-val[u])*(val[v]-val[u])*(val[v]-val[u]));
}
spfa(1);
cout << "Case " << ++cnt << ":" << endl;
int q ;
scanf("%lld" , &q);
rep(i , 1 , q){
int x ;
scanf("%lld" , &x);
if(f[x] || dis[x] == INF || dis[x] < 3){
cout << "?" << endl;
}else{
cout << dis[x] << endl;
}
}
}
signed main()
{
//ios::sync_with_stdio(false);
int t ;
scanf("%lld" , &t);
while(t--)
solve();
}