fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define ii pair<int,int>
  5. #define iii pair<int, ii>
  6. #define iiii pair<ii,ii>
  7. #define fi first
  8. #define se second
  9. #define inf 10000000000000000
  10. #define pi M_PI
  11. const int N = 1e5 + 5;
  12. int n, m;
  13. int S, T, X, Y;
  14. vector<ii> g[N];
  15. int dx[3*N], dn[N];
  16. vector<ii> g2[3*N], g3[3*N];
  17. vector<iii> canh;
  18. signed main() {
  19.     ios_base::sync_with_stdio(0);
  20.     cin.tie(0);
  21.     cout.tie(0);
  22.     if(fopen("main.inp","r")) {
  23.         freopen("main.inp", "r", stdin);
  24.         freopen("main.out", "w", stdout);
  25.     }
  26.     cin >> n >> m;
  27.     cin >> S >> T >> X >> Y;
  28.     for(int i = 1; i <= m; i++) {
  29.         int u, v, w;
  30.         cin >> u >> v >> w;
  31.         g[u].push_back({w,v});
  32.         g[v].push_back({w,u});
  33.         canh.push_back({w,{u,v}});
  34.     }
  35.  
  36.  
  37.     priority_queue<ii,vector<ii>,greater<ii>> pq;
  38.     for(int i = 1; i <= n; i++) dx[i] = inf;
  39.     dx[S] = 0;
  40.     pq.push({0,S});
  41.     while(pq.size()) {
  42.         int u = pq.top().se;
  43.         int du = pq.top().fi;
  44.         pq.pop();
  45.         if(du != dx[u]) continue;
  46.         for(auto tmp : g[u]) {
  47.             int v = tmp.se;
  48.             int w = tmp.fi;
  49.             if(dx[v] > dx[u] + w) {
  50.                 dx[v] = dx[u] + w;
  51.                 pq.push({dx[v],v});
  52.             }
  53.         }
  54.     }
  55.  
  56.     for(int i = 1; i <= n; i++) dn[i] = inf;
  57.     dn[T] = 0;
  58.     pq.push({0,T});
  59.     while(pq.size()) {
  60.         int u = pq.top().se;
  61.         int du = pq.top().fi;
  62.         pq.pop();
  63.         if(du != dn[u]) continue;
  64.         for(auto tmp : g[u]) {
  65.             int v = tmp.se;
  66.             int w = tmp.fi;
  67.             if(dn[v] > dn[u] + w) {
  68.                 dn[v] = dn[u] + w;
  69.                 pq.push({dn[v],v});
  70.             }
  71.         }
  72.     }
  73.  
  74.     for(auto x : canh) {
  75.             int i = x.se.fi;
  76.             int j = x.se.se;
  77.             int w = x.fi;
  78.             if(dx[i] + w + dn[j] == dx[T]) {
  79.             g3[i].push_back({0,j});
  80.             }
  81.             if(dx[j] + w + dn[i] == dx[T]) {
  82.                 g3[j].push_back({0,i});
  83.             }
  84.  
  85.  
  86.     }
  87.  
  88.     for(auto tmp : canh) {
  89.             int i = tmp.se.fi;
  90.             int j = tmp.se.se;
  91.             int w = tmp.fi;
  92.             g3[i+n].push_back({w,j+n});
  93.             g3[j+n].push_back({w,i+n});
  94.             g3[i+2*n].push_back({w,j+2*n});
  95.             g3[j+2*n].push_back({w,i+2*n});
  96.             g3[i+n].push_back({0,i});
  97.             g3[j+n].push_back({0,j});
  98.             g3[i].push_back({0,i+2*n});
  99.             g3[j].push_back({0,j+2*n});
  100.     }
  101.     for(int i = 1; i <= 3*n; i++) dx[i] = inf;
  102.     dx[Y+n] = 0;
  103.     pq.push({0,Y+n});
  104.     while(pq.size()) {
  105.         int u = pq.top().se;
  106.         int du = pq.top().fi;
  107.         pq.pop();
  108.         if(du != dx[u]) continue;
  109.         for(auto tmp : g3[u]) {
  110.             int v = tmp.se;
  111.             int w = tmp.fi;
  112.             if(dx[v] > dx[u] + w) {
  113.                 dx[v] = dx[u] + w;
  114.                 pq.push({dx[v],v});
  115.             }
  116.         }
  117.     }
  118.     int ans = dx[X+2*n];
  119.     for(int i = 1; i <= 3*n; i++) dx[i] = inf;
  120.     dx[X+n] = 0;
  121.     pq.push({0,X+n});
  122.     while(pq.size()) {
  123.         int u = pq.top().se;
  124.         int du = pq.top().fi;
  125.         pq.pop();
  126.         if(du != dx[u]) continue;
  127.         for(auto tmp : g3[u]) {
  128.             int v = tmp.se;
  129.             int w = tmp.fi;
  130.             if(dx[v] > dx[u] + w) {
  131.                 dx[v] = dx[u] + w;
  132.                 pq.push({dx[v],v});
  133.             }
  134.         }
  135.     }
  136.     ans = min(ans,dx[Y+2*n]);
  137.     cout << ans;
  138.     return 0;
  139. }
Success #stdin #stdout 0.01s 23108KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/RSGwS4
language:
C++14 (gcc 8.3)
created:
7 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!