ccbeginner

UVa Q10039 (!finish)

Feb 6th, 2020
171
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int arr[100][1000];
  5. bool vis[100][1000];
  6. struct stat{
  7.     int V, tr, early;
  8.     bool operator>(const stat &x)const{
  9.         if(arr[V][tr] == arr[x.V][x.tr])return early < x.early;
  10.         return arr[V][tr] > arr[x.V][x.tr];
  11.     }
  12. };
  13. map<string, int> mp;
  14. string v[100];
  15.  
  16. int main(){
  17.     int t, n, m, T;
  18.     string s;
  19.     cin >> t;
  20.     for(int k = 1; k <= t; ++k){
  21.         memset(vis, 0, sizeof(vis));
  22.         cin >> n;//cities
  23.         for(int i = 0; i < n; ++i){
  24.             cin >> s;
  25.             mp[s] = i;
  26.             v[i] = s;
  27.         }
  28.         cin >> n;//trains
  29.         for(int i = 0; i < n; ++i){
  30.             for(unsigned j = 0; j < mp.size(); ++j)arr[j][i] = -1;
  31.             cin >> m;
  32.             while(m--){
  33.                 cin >> T >> s;
  34.                 arr[mp[s]][i] = T;
  35.             }
  36.         }
  37.         cin >> T >> s;
  38.         stat one;
  39.         one.V = mp[s];
  40.         cin >> s;//destination
  41.         priority_queue<stat, deque<stat>, greater<stat> > pq;
  42.         for(int i = 0; i < n; ++i){//trains
  43.             if(arr[one.V][i] >= T){
  44.                 one.tr = i;
  45.                 one.early = arr[one.V][i];
  46.                 pq.push(one);
  47.             }
  48.         }
  49.         int depart=-1, arrive=-1;
  50.         while(!pq.empty()){
  51.             stat tmd = pq.top();
  52.             pq.pop();
  53.             //cout << v[tmd.V] << ' ' << tmd.tr << ' ' << arr[tmd.V][tmd.tr] << ' ' << tmd.early << endl;
  54.             if(vis[tmd.V][tmd.tr])continue;
  55.             if(v[tmd.V] == s){
  56.                 depart = tmd.early;
  57.                 arrive = arr[tmd.V][tmd.tr];
  58.                 break;
  59.             }
  60.             vis[tmd.V][tmd.tr] = 1;
  61.             for(int i = 0; i < n; ++i){//change train
  62.                 if(vis[tmd.V][i] || arr[tmd.V][tmd.tr] > arr[tmd.V][i])continue;
  63.                 stat nxt = tmd;
  64.                 nxt.tr = i;
  65.                 pq.push(nxt);
  66.             }
  67.             for(unsigned i = 0; i < mp.size(); ++i){//change place
  68.                 if(vis[i][tmd.tr] || arr[tmd.V][tmd.tr] > arr[i][tmd.tr])continue;
  69.                 stat nxt = tmd;
  70.                 nxt.V = i;
  71.                 pq.push(nxt);
  72.             }
  73.         }
  74.         cout << "Scenario " << k << '\n';
  75.         if(depart == -1 && arrive == -1)cout << "No connection\n";
  76.         else{
  77.             printf("Departure %04d ", depart);
  78.             cout << v[one.V] << '\n';
  79.             printf("Arrival   %04d ", arrive);
  80.             cout << s << '\n';
  81.         }
  82.         cout << '\n';
  83.     }
  84.     return 0;
  85. }
RAW Paste Data