ccbeginner

UVa Q11374

Feb 1st, 2020
120
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //UVa 11374
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. struct stat{
  6.     int pre, v, w;
  7.     int used;
  8.     bool operator>(const stat &x)const{return w > x.w;}
  9. };
  10. vector<stat> edges[505];
  11. int preV[1005];//1~n := not used, n+1~2n := used
  12.  
  13. int main(){
  14.     int n,s,e,m,a,b,c;
  15.     bool one = 1;
  16.     while(cin >> n >> s >> e){
  17.         if(one)one = 0;
  18.         else cout << '\n';
  19.         memset(preV, 0, sizeof(preV));
  20.         for(int i = 1; i <= n; ++i)edges[i].clear();
  21.         cin >> m;
  22.         for(int i = 0; i < m; ++i){
  23.             cin >> a >> b >> c;
  24.             stat in={.pre=a, .v=b, .w=c, .used=0};
  25.             edges[a].emplace_back(in);
  26.             in={.pre=b, .v=a, .w=c, .used=0};
  27.             edges[b].emplace_back(in);
  28.         }
  29.         cin >> m;
  30.         for(int i = 0; i < m; ++i){
  31.             cin >> a >> b >> c;
  32.             stat in={.pre=a, .v=b, .w=c, .used=a};
  33.             edges[a].emplace_back(in);
  34.             in={.pre=b, .v=a, .w=c, .used=b};
  35.             edges[b].emplace_back(in);
  36.         }
  37.         priority_queue<stat, deque<stat>, greater<stat>> pq;
  38.         stat tmd = {.pre=-1, .v=s, .w=0, .used=0};
  39.         pq.push(tmd);
  40.         stat ans;
  41.         while(!pq.empty()){
  42.             tmd = pq.top();
  43.             pq.pop();
  44.             //cout << tmd.pre << ' ' << tmd.v << ' ' << tmd.w << ' ' << tmd.used << '\n';
  45.             int idx = (tmd.used)? tmd.v+n : tmd.v;
  46.             if(!preV[idx])preV[idx] = tmd.pre;
  47.             else continue;
  48.             if(tmd.v == e){
  49.                 ans = tmd;
  50.                 break;
  51.             }
  52.             for(unsigned i = 0; i < edges[tmd.v].size(); ++i){
  53.                 stat nxt = edges[tmd.v][i];
  54.                 idx = (nxt.used | tmd.used)? nxt.v+n : nxt.v;
  55.                 if(!preV[idx] && (tmd.used == 0 || nxt.used == 0)){
  56.                     if(tmd.used > 0)nxt.pre += n;
  57.                     nxt.w += tmd.w;
  58.                     nxt.used |= tmd.used;
  59.                     pq.push(nxt);
  60.                 }
  61.             }
  62.         }
  63.         vector<int> out;
  64.         int x = (ans.used)? ans.v+n : ans.v;
  65.         while(x != -1){
  66.             out.emplace_back((x>n)? x-n : x);
  67.             x = preV[x];
  68.         }
  69.         while(!out.empty()){
  70.             cout << out.back();
  71.             out.pop_back();
  72.             if(!out.empty())cout << ' ';
  73.         }
  74.         cout << '\n';
  75.         if(ans.used == 0)cout << "Ticket Not Used";
  76.         else cout << ans.used;
  77.         cout << '\n' << ans.w << '\n';
  78.     }
  79.     return 0;
  80. }
RAW Paste Data