Advertisement
YEZAELP

CUBE-196: Royal Parade

Sep 3rd, 2020
202
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.57 KB | None
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using lli = long long;
  5. const lli INF = 2e18;
  6. using pil = pair <int, lli>;
  7. using pli = pair <lli, int>;
  8. int n, m, A, B, C, D;
  9. vector <pil> g[100001];
  10. vector < vector <lli>> dis(3, vector <lli> (100001, INF));
  11.  
  12. lli find_distance(int start, int opr){
  13.  
  14.     vector <int> visited(n + 1, false);
  15.     priority_queue <pli, vector <pli>, greater <pli>> pq;
  16.     pq.push({0, start});
  17.     dis[opr][start] = 0;
  18.  
  19.     while(pq.size() > 0){
  20.         lli d = pq.top().first;
  21.         int u = pq.top().second;
  22.         pq.pop();
  23.  
  24.         if(visited[u])
  25.             continue;
  26.         visited[u] = true;
  27.  
  28.         if(opr == 2 and u == D) return d;
  29.  
  30.         for(auto vw: g[u]){
  31.             int v = vw.first;
  32.             lli w = vw.second;
  33.             if(opr == 2){
  34.                 if(dis[0][v] + dis[1][v] != dis[0][B]){
  35.                     dis[opr][v] = d + w;
  36.                     pq.push({dis[opr][v], v});
  37.                 }
  38.                 continue;
  39.             }
  40.             if(!visited[v] and d + w < dis[opr][v]){
  41.                 dis[opr][v] = d + w;
  42.                 pq.push({dis[opr][v], v});
  43.             }
  44.         }
  45.     }
  46.     return -1;
  47. }
  48.  
  49. int main(){
  50.  
  51.     scanf("%d%d", &n, &m);
  52.  
  53.     for(int i = 1; i <= m; i++){
  54.         int u, v;
  55.         lli w;
  56.         scanf("%d%d%lld", &u, &v, &w);
  57.         g[u].push_back({v, w});
  58.         g[v].push_back({u, w});
  59.     }
  60.  
  61.     scanf("%d%d%d%d", &A, &B, &C, &D);
  62.  
  63.     find_distance(A, 0);
  64.     find_distance(B, 1);
  65.  
  66.     printf("%lld",find_distance(C, 2));
  67.  
  68.     return 0;
  69. }
  70.  
Advertisement
RAW Paste Data Copied
Advertisement