UVa Q10039 (!finish)

#include <bits/stdc++.h>
using namespace std;

int arr[100][1000];
bool vis[100][1000];
struct stat{
    int V, tr, early;
    bool operator>(const stat &x)const{
        if(arr[V][tr] == arr[x.V][x.tr])return early < x.early;
        return arr[V][tr] > arr[x.V][x.tr];
    }
};
map<string, int> mp;
string v[100];

int main(){
    int t, n, m, T;
    string s;
    cin >> t;
    for(int k = 1; k <= t; ++k){
        memset(vis, 0, sizeof(vis));
        cin >> n;//cities
        for(int i = 0; i < n; ++i){
            cin >> s;
            mp[s] = i;
            v[i] = s;
        }
        cin >> n;//trains
        for(int i = 0; i < n; ++i){
            for(unsigned j = 0; j < mp.size(); ++j)arr[j][i] = -1;
            cin >> m;
            while(m--){
                cin >> T >> s;
                arr[mp[s]][i] = T;
            }
        }
        cin >> T >> s;
        stat one;
        one.V = mp[s];
        cin >> s;//destination
        priority_queue<stat, deque<stat>, greater<stat> > pq;
        for(int i = 0; i < n; ++i){//trains
            if(arr[one.V][i] >= T){
                one.tr = i;
                one.early = arr[one.V][i];
                pq.push(one);
            }
        }
        int depart=-1, arrive=-1;
        while(!pq.empty()){
            stat tmd = pq.top();
            pq.pop();
            //cout << v[tmd.V] << ' ' << tmd.tr << ' ' << arr[tmd.V][tmd.tr] << ' ' << tmd.early << endl;
            if(vis[tmd.V][tmd.tr])continue;
            if(v[tmd.V] == s){
                depart = tmd.early;
                arrive = arr[tmd.V][tmd.tr];
                break;
            }
            vis[tmd.V][tmd.tr] = 1;
            for(int i = 0; i < n; ++i){//change train
                if(vis[tmd.V][i] || arr[tmd.V][tmd.tr] > arr[tmd.V][i])continue;
                stat nxt = tmd;
                nxt.tr = i;
                pq.push(nxt);
            }
            for(unsigned i = 0; i < mp.size(); ++i){//change place
                if(vis[i][tmd.tr] || arr[tmd.V][tmd.tr] > arr[i][tmd.tr])continue;
                stat nxt = tmd;
                nxt.V = i;
                pq.push(nxt);
            }
        }
        cout << "Scenario " << k << '\n';
        if(depart == -1 && arrive == -1)cout << "No connection\n";
        else{
            printf("Departure %04d ", depart);
            cout << v[one.V] << '\n';
            printf("Arrival   %04d ", arrive);
            cout << s << '\n';
        }
        cout << '\n';
    }
    return 0;
}