传送门
#include <iostream>
#include <map>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010, INF = 0x3f3f3f3f;
struct Edge{
int u, v, w, next;
}edge[4e5 + 10];
bool vis[N], flag = false;
int tot = 1, head[N], n, q, a[N], cnt[N], dist[N];
void add(int u, int v, int w){
edge[tot].w = w;
edge[tot].v = v;
edge[tot].next = head[u];
head[u] = tot ++;
}
int cal(int x){
return x * x * x;
}
bool spfa(int s){
queue<int> qq;
memset(cnt, 0, sizeof cnt);
memset(dist, INF, sizeof dist);
memset(vis, 0, sizeof vis);
dist[s] = 0;
qq.push(s);
vis[s] = 1;
while(qq.size()){
int t = qq.front();
qq.pop();
vis[t] = 0;
for(int i = head[t]; i; i = edge[i].next){
int w = edge[i].w;
int to = edge[i].v;
if(dist[to] > w + dist[t]){
dist[to] = w + dist[t];
cnt[to] = cnt[t] + 1; //change
if(cnt[to] >= n)
return true;
if(!vis[to]){
vis[to] = true;
qq.push(to);
}
}
}
}
}
int main(){
int t, k = 0;
cin >> t;
while(t --){
memset(head, 0, sizeof head);
cout << "Case " << ++ k << ":" << endl;
cin >> n;
for(int i = 1; i <= n; i ++)
cin >> a[i];
cin >> q;
while(q --){
int x, y;
cin >> x >> y;
add(x, y, cal(a[y] - a[x]));
}
spfa(1);
int query;
cin >> query;
while(query --){
int des;
cin >> des;
if(dist[des] >= INF / 2 || dist[des] < 3)
cout << '?' << endl;
else
cout << dist[des] << endl;
}
}
return 0;
}