RDNWK - Road Network SPOJ Solution

 #include <bits/stdc++.h>
using namespace std;
#define mx ((int)1e9)
int n,p,q;
vector<vector<int> > g;
vector<vector<vector<int> > > d;
int rnk[151];
void floyd(){
    for(int k=1;k<=p;k++)
        for(int i=1;i<=n;i++)
            d[k][i][i]=0;
    for(int x=1;x<=p;x++){
        int k=rnk[x];
        d[x]=d[x-1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                d[x][i][j]=min(d[x][i][j],d[x][i][k]+d[x][k][j]);
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    int t;
    cin>>t;
    int cs=0;
    while(cs<t){
        cout<<"Case "<<++cs<<":";
    cin>>n;
    g.assign(n+1,vector<int>(n+1,0));
    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++){
            cin>>g[i][j];
            if(g[i][j]==-1)
                g[i][j]=mx;
            g[j][i]=g[i][j];
        }
    }
    cin>>p;
    for(int i=1;i<=p;i++)
        cin>>rnk[i];
    d.assign(p+1,vector<vector<int> >(n+1,vector<int>(n+1,mx)));
    d[0]=g;
    floyd();
    cin>>q;
    for(int i=0;i<q;i++){
        int k,so,de;
        cin>>k>>so>>de;
        cout<<' '<<((d[k][so][de]==mx)?-1:d[k][so][de]);
    }
    cout<<'\n';
}
return 0;
}