ccbeginner

UVa Q10187

Feb 4th, 2020
156
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //UVa Q10187
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. struct stat{
  6.     int city, T, blood;
  7.     bool operator>(const stat &x)const{return blood > x.blood;}
  8. };
  9. vector<int> route[105], start[105], ended[105];
  10. map<string, int> mp;
  11. int vis[105][12];
  12.  
  13. int main(){
  14.     int t, n, a, b, cnt = 0;
  15.     string s1, s2;
  16.     cin >> t;
  17.     while(t--){
  18.         cin >> n;
  19.         int k = 0;
  20.         mp.clear();
  21.         memset(vis, 0, sizeof(vis));
  22.         for(int i = 0; i < 100; ++i){
  23.             route[i].clear();
  24.             start[i].clear();
  25.             ended[i].clear();
  26.         }
  27.         for(int i = 0; i < n; ++i){
  28.             cin >> s1 >> s2 >> a >> b;
  29.             if((6 <= a && a < 18) || (6 < (a+b)%24 && (a+b)%24 <= 18) || b > 12)continue;
  30.             if(mp.find(s1) == mp.end())mp[s1] = k++;
  31.             if(mp.find(s2) == mp.end())mp[s2] = k++;
  32.             route[mp[s1]].emplace_back(mp[s2]);
  33.             a = (a >= 18)? a-18 : a+6;
  34.             start[mp[s1]].emplace_back(a);
  35.             ended[mp[s1]].emplace_back(a+b);
  36.             //cout << s1 << ' ' << s2 << ' ' << a << ' ' << b << endl;
  37.         }
  38.         cin >> s1 >> s2;
  39.         if(mp.find(s1) == mp.end())mp[s1] = k++;
  40.         if(mp.find(s2) == mp.end())mp[s2] = k++;
  41.         stat one = {.city = mp[s1], .T = 0, .blood = 0};
  42.         priority_queue<stat, deque<stat>, greater<stat> > pq;
  43.         pq.push(one);
  44.         int ans = -1;
  45.         while(!pq.empty()){
  46.             stat tmd = pq.top();
  47.             pq.pop();
  48.             //cout << tmd.city << ' ' << tmd.T << ' ' << tmd.blood << endl;
  49.             if(!vis[tmd.city][tmd.T])vis[tmd.city][tmd.T] = 1;
  50.             else continue;
  51.             if(tmd.city == mp[s2]){
  52.                 ans = tmd.blood;
  53.                 break;
  54.             }
  55.             for(unsigned i = 0; i < route[tmd.city].size(); ++i){
  56.                 stat nxt = {.city = route[tmd.city][i],
  57.                             .T = ended[tmd.city][i],
  58.                             .blood = (tmd.T <= start[tmd.city][i])? tmd.blood : tmd.blood+1};
  59.                 //cout << ' ' << nxt.city << ' ' << nxt.T << ' ' << nxt.blood << endl;
  60.                 if(!vis[nxt.city][nxt.T])pq.push(nxt);
  61.             }
  62.         }
  63.         cout << "Test Case " << ++cnt << ".\n";
  64.         if(ans == -1)cout << "There is no route Vladimir can take.\n";
  65.         else cout << "Vladimir needs " << ans << " litre(s) of blood.\n";
  66.     }
  67.     return 0;
  68. }
RAW Paste Data