ccbeginner

UVa Q544

Jan 29th, 2020
111
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //UVa Q544
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. struct stat{
  6.     int V, W;
  7.     bool operator<(const stat &x)const{return W < x.W;}
  8. };
  9.  
  10. vector<stat> v[200];
  11. bool vis[200];
  12.  
  13. int32_t main(){
  14.     int n,m,x, cnt = 0;
  15.     while(cin >> n >> m){
  16.         if(n == 0 && m == 0)break;
  17.         for(int i = 0; i < n; ++i){
  18.             v[i].clear();
  19.             vis[i] = 0;
  20.         }
  21.         string s1, s2;
  22.         map<string, int> cite;
  23.         map<string, int>::iterator it;
  24.         int k = 0;
  25.         for(int i = 0; i < m; ++i){
  26.             cin >> s1 >> s2 >> x;
  27.             it = cite.find(s1);
  28.             if(it == cite.end())cite[s1] = k++;
  29.             it = cite.find(s2);
  30.             if(it == cite.end())cite[s2] = k++;
  31.             stat in = {.V = cite[s2], .W = x};
  32.             v[cite[s1]].emplace_back(in);
  33.             in = {.V = cite[s1], .W = x};
  34.             v[cite[s2]].emplace_back(in);
  35.         }
  36.         cin >> s1 >> s2;
  37.         int start = cite[s1];
  38.         int ended = cite[s2];
  39.         priority_queue<stat> pq;
  40.         stat tmd = {.V=start, .W=1000000000};
  41.         pq.push(tmd);
  42.         int ans = -1;
  43.         while(!pq.empty() && ans == -1){
  44.             tmd = pq.top();
  45.             pq.pop();
  46.             vis[tmd.V] = 1;
  47.             //cout << tmd.V << ' ' << tmd.W<<endl;
  48.             if(tmd.V == ended){
  49.                 ans = tmd.W;
  50.                 break;
  51.             };
  52.             for(unsigned i = 0; i < v[tmd.V].size(); ++i){
  53.                 if(!vis[v[tmd.V][i].V]){
  54.                     stat in = v[tmd.V][i];
  55.                     in.W = min(in.W, tmd.W);
  56.                     pq.push(in);
  57.                 }
  58.             }
  59.         }
  60.         cout << "Scenario #" << ++cnt << '\n';
  61.         cout << ans << " tons\n\n";
  62.     }
  63.     return 0 ;
  64. }
RAW Paste Data