ccbeginner

UVa Q721

Jan 30th, 2020
138
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //UVa Q721
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define int long long
  5. const int MAXN = 1e6+1;
  6.  
  7. struct stat{
  8.     int v, w;
  9.     bool operator>(const stat &x)const{return w > x.w;}
  10. };
  11. vector<stat> e1[MAXN];
  12. vector<stat> e2[MAXN];
  13. int ans1[MAXN];
  14. int ans2[MAXN];
  15.  
  16. int32_t main(){
  17.     int t,n,m;
  18.     cin >> t;
  19.     while(t--){
  20.         cin >> n >> m;
  21.         for(int i = 1; i <= n; ++i){
  22.             e1[i].clear();
  23.             e2[i].clear();
  24.             ans1[i] = ans2[i] = 1e18;
  25.         }
  26.         for(int i = 0; i < m; ++i){
  27.             int a,b,c;
  28.             cin >> a >> b >> c;
  29.             stat aux={.v = b, .w = c};
  30.             e1[a].emplace_back(aux);
  31.             aux.v = a;
  32.             e2[b].emplace_back(aux);
  33.         }
  34.         priority_queue<stat, deque<stat>, greater<stat> > pq1, pq2;
  35.         stat tmd={.v = 1, .w = 0};
  36.         pq1.push(tmd);
  37.         pq2.push(tmd);
  38.         while(!pq1.empty()){
  39.             tmd = pq1.top();
  40.             pq1.pop();
  41.             //cout << tmd.v << ' ' << tmd.w << ' ' << endl;
  42.             if(ans1[tmd.v] == 1e18)ans1[tmd.v] = tmd.w;
  43.             for(unsigned i = 0; i < e1[tmd.v].size(); ++i){
  44.                 if(ans1[e1[tmd.v][i].v] != 1e18)continue;
  45.                 stat nxt = e1[tmd.v][i];
  46.                 nxt.w += tmd.w;
  47.                 pq1.push(nxt);
  48.             }
  49.         }
  50.         /*for(int i = 1; i <= n; ++i){
  51.             cout << ans1[i] << ' ';
  52.         }
  53.         cout << endl;*/
  54.         while(!pq2.empty()){
  55.             tmd = pq2.top();
  56.             pq2.pop();
  57.             //cout << tmd.v << ' ' << tmd.w << ' ' << endl;
  58.             if(ans2[tmd.v] == 1e18)ans2[tmd.v] = tmd.w;
  59.             for(unsigned i = 0; i < e2[tmd.v].size(); ++i){
  60.                 if(ans2[e2[tmd.v][i].v] != 1e18)continue;
  61.                 stat nxt = e2[tmd.v][i];
  62.                 nxt.w += tmd.w;
  63.                 pq2.push(nxt);
  64.             }
  65.         }
  66.         /*for(int i = 1; i <= n; ++i){
  67.             cout << ans2[i] << ' ';
  68.         }
  69.         cout << endl;*/
  70.         int out = 0;
  71.         for(int i = 1; i <= n; ++i)out += ans1[i]+ans2[i];
  72.         cout << out << '\n';
  73.     }
  74.     return 0 ;
  75. }
RAW Paste Data