Joao_Joao

WA - 2566 - Viagem Para BH - C++

Nov 2nd, 2020 (edited)
125
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. # define vt vector
  5. # define pque priority_queue
  6. typedef long long ll;typedef long double lld;typedef string str;typedef pair<double, double> dd;
  7. typedef vt<int> vi;typedef vt<vt<int>> vvi;typedef vt<double> vd;typedef vt<ll> vll;typedef pair<int,int> ii;
  8. typedef vt<lld> vld;typedef vt<char> vc;typedef vt<str> vs;typedef vt<ii> vii;typedef vt<vii> vvii;
  9. # define f(i,a,b,c) for(ll i=a;i<b;i+=c)
  10. # define fd(i,a,b,c) for(ll i=a;i>=b;i-=c)
  11. # define w(x) while(x--)
  12. # define ctoi(a) (a-'0')
  13. # define pb push_back
  14. # define eb emplace_back
  15. # define lb lower_bound
  16. # define ub upper_bound
  17. # define len(x) x.length()
  18. # define be(x) x.begin(), x.end()
  19. # define rbe(x) x.rbegin(), x.rend()
  20. # define bb binary_search
  21. # define _(x) cout.precision(x);cout.setf(ios::fixed);
  22. # define ft first
  23. # define se second
  24.  
  25. const int MAX = 1<<10, MAXN = 101, MAXM  = 2e4+1, INF = INT_MAX;
  26.  
  27. int n, m;
  28. int u, v, t, w, a, b, pos1, pos2, ou1, ou2;
  29. vvii gr1, gr2;
  30. vi dist1, dist2;
  31.  
  32. int dijkstra1(int s, int t){
  33.     if(pos1==1)return gr1[ou1][0].se;
  34.     dist1 = vi(n+1, INF);
  35.     pque<ii, vii, greater<ii>> pq;
  36.     dist1[s] = 0, pq.push(ii(dist1[s], s));
  37.     while(!pq.empty()){
  38.         ii topo = pq.top();pq.pop();
  39.         int d = topo.ft, u = topo.se;
  40.    
  41.         if(d > dist1[u])continue;
  42.         if(u==t){return dist1[t];}
  43.         //if(u==t)return dist[t];
  44.         for(auto [v, w]:gr1[u]){
  45.             if(dist1[u] + w < dist1[v]){
  46.                 dist1[v] = dist1[u] + w;
  47.                 //cout<<v<<' '<<dist1[v]<<' '<<w<<'\n';
  48.                 pq.push(ii(dist1[v], v));
  49.             }
  50.         }
  51.     }
  52.     return INF;
  53. }
  54.  
  55. int dijkstra2(int s, int t){
  56.     if(pos2==1)return gr2[ou2][0].se;
  57.     dist2 = vi(n+1, INF);
  58.     pque<ii, vii, greater<ii>> pq;
  59.     dist2[s] = 0, pq.push(ii(dist2[s], s));
  60.     while(!pq.empty()){
  61.         ii topo = pq.top();pq.pop();
  62.         int d = topo.ft, u = topo.se;
  63.    
  64.         if(d > dist2[u])continue;
  65.         if(u==t){return dist2[t];}
  66.         //if(u==t)return dist[t];
  67.         for(auto [v, w]:gr2[u]){
  68.             if(dist2[u] + w < dist2[v]){
  69.                 dist2[v] = dist2[u] + w;
  70.                 //cout<<v<<' '<<dist2[v]<<' '<<w<<'\n';
  71.                 pq.push(ii(dist2[v], v));
  72.             }
  73.         }
  74.     }
  75.     return INF;
  76. }
  77.  
  78. int main(){_(0)
  79.     while(cin>>n>>m){
  80.     //if(m==1){cin>>u>>v>>t>>w;cout<<w<<'\n';}
  81.         if(m==1){cin>>u>>v>>t>>w;cout<<w<<'\n';}
  82.         else{
  83.             pos1 = 0, pos2 = 0;
  84.             gr1 = vvii(n+1), gr2 = vvii(n+1);
  85.             f(i,0,m,1){
  86.                 cin>>u>>v>>t>>w;
  87.                 if(t == 0)gr1[u].eb(v, w), ++pos1, ou1 = u;
  88.                 else gr2[u].eb(v, w), ++pos2, ou2 = u;
  89.             }
  90.             a = dijkstra1(1, n), b = dijkstra2(1, n);
  91.            
  92.             //cout<<a<<' '<<b<<'\n';
  93.             cout<<min(a, b)<<'\n';
  94.         }
  95.     }
  96. return 0;}
RAW Paste Data Copied