Negative Cycle

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace   std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;

typedef long long ll;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define     sz                 size()
#define     pb                 push_back
#define     inf                (1<<30)
#define     mod                (1000000007)
#define     pi                 (acos(-1.0))
#define     rep(i, n)          for(__typeof(n) i=0; i<(n); i++)
#define     foab(i, a, b)      for(__typeof(b) i=(a); i<=(b); i++)
#define     foba(i, a, b)      for(__typeof(b) i=(b); i>=(a); i--)
#define     foch(it, l)        for(__typeof((l).begin()) it = (l).begin();  it != (l).end(); ++it)
#define     what_is_x(x)       cout << (#x) << " is " << (x) << endl;

template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> ostream& operator<<(ostream& os, const vector<T> &t) { ll n = t.size(); rep(i, n) os<<t[i]<<" "; return os; }
template<typename T,typename TT> ostream& operator<<(ostream &os, const pair<T,TT> &t) { return os<<"("<<t.first<<","<<t.second<<")"; }
/**__________________________________________________________________________________________________________________________________*/


struct data{
    int u, v, w;
    int prevIndx;
}edgeList[205];


int ara[205];
int d[205];
bool cycle[205];
int lastIndx[205];
int nodes, edges;

void dfs(int u){
    if(!cycle[u]){
        cycle[u] = true;
        for(int e = lastIndx[u] ; e != -1 ; e = edgeList[e].prevIndx){
            int v = edgeList[e].v;
            dfs(v);
        }
    }
}

void bellmanFord(int source = 1){
    foab(i, 1, nodes){
        d[i] = inf;
        cycle[i] = false;
    }

    d[source] = 0;

    foab(i, 1, nodes-1){
        foab(j, 1, edges){
            int u = edgeList[j].u, v = edgeList[j].v, w = edgeList[j].w;
            if(d[u] < inf){
                if(d[v] > d[u] + w){
                    d[v] = d[u] + w;
                }
            }
        }
    }

    foab(j, 1, edges){
        int u = edgeList[j].u, v = edgeList[j].v, w = edgeList[j].w;
        if(d[u] < inf && !cycle[u]){
            if(d[v] > d[u] + w){
                dfs(u);
            }
        }
    }
}



int main(){
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int T;cin>>T;
    foab(t, 1, T){
        cin>>nodes;
        foab(i, 1, nodes){
            cin>>ara[i];
            lastIndx[i] = -1;
        }
        cin>>edges;
        foab(i, 1, edges){
            int u, v;
            cin>>u>>v;
            edgeList[i].u = u, edgeList[i].v = v, edgeList[i].w = (ara[v] - ara[u])*(ara[v] - ara[u])*(ara[v] - ara[u]);
            edgeList[i].prevIndx = lastIndx[u];
            lastIndx[u] = i;
        }

        bellmanFord(1);

        int q;
        cin>>q;
        cout<<"Case "<<t<<":\n";
        while(q--){
            int vv;
            cin>>vv;
            if(cycle[vv] || d[vv] == inf || d[vv] < 3){
                cout<<"?"<<endl;
            }
            else{
                cout<<d[vv]<<endl;
            }
        }

    }

    return 0;

}