fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. #define s second
  5. #define f first
  6. typedef pair<ll, ll> pii;
  7.  
  8. const ll INF = 1e16;
  9. const int N = 1e5 + 1;
  10. vector<pii> graf[N];
  11.  
  12.  
  13. void dijkstra(int start, vector<ll>& odl){
  14.     odl[start] = 0;
  15.     priority_queue<pii, vector<pii>, greater<pii>> pq;
  16.     pq.push({0, start});
  17.  
  18.     while(!pq.empty()){
  19.         ll w = pq.top().f;
  20.         ll v = pq.top().s;
  21.         pq.pop();
  22.  
  23.         if(w > odl[v]) continue;
  24.         for(pii x : graf[v]){
  25.             ll u = x.f;
  26.             ll waga = x.s;
  27.  
  28.             ll n_dyst = waga + w;
  29.             if(n_dyst < odl[u]){
  30.                 odl[u] = n_dyst;
  31.                 pq.push({n_dyst, u});
  32.             }
  33.         }
  34.     }
  35.  
  36. }
  37.  
  38.  
  39. int main(){
  40.     ios_base::sync_with_stdio(0);
  41.     cin.tie(0);
  42.  
  43.  
  44.     int n, m;
  45.     cin >> n >> m;
  46.  
  47.     int s, t, u, v;
  48.     cin >> s >> t >> u >> v;
  49.  
  50.     vector<pair<pair<int, int>, ll>> kraw(m);
  51.     vector<int> graf2[n + 1], graf3[n + 1];
  52.     for(int i = 0; i < m; i++){
  53.         int a, b, c;
  54.         cin >> a >> b >> c;
  55.         graf[a].push_back({b, c});
  56.         graf[b].push_back({a, c});
  57.         kraw[i] = {{a, b}, c};
  58.     }
  59.  
  60.     vector<ll> du(N, INF), dv(N, INF), ds(N, INF), dt(N, INF);
  61.  
  62.     dijkstra(s, ds);
  63.     dijkstra(v, dv);
  64.     dijkstra(t, dt);
  65.     dijkstra(u, du);
  66.  
  67.     ll najk = ds[t];
  68.     vector<int> czy(N, 0);
  69.     vector<int> topo1, topo2;
  70.     for(int i = 1; i <= n; i++){
  71.         if(ds[i] + dt[i] == najk && najk != INF){
  72.             czy[i] = 1;
  73.         }
  74.     }
  75.  
  76.     vector<int> stopien1(n + 1, 0), stopien2(n + 1, 0);
  77.     for(auto kr : kraw){
  78.         int a = kr.f.f, b = kr.f.s;
  79.         int w = kr.s;
  80.  
  81.         if(ds[a] + w == ds[b] && czy[a] == 1 && czy[b] == 1){
  82.             graf2[a].push_back(b);
  83.             stopien1[b]++;
  84.         }
  85.         if(ds[b] + w == ds[a] && czy[a] == 1 && czy[b] == 1){
  86.             graf2[b].push_back(a);
  87.             stopien1[a]++;
  88.         }
  89.         if(dt[a] + w == dt[b] && czy[a] == 1 && czy[b] == 1){
  90.             graf3[a].push_back(b);
  91.             stopien2[b]++;
  92.         }
  93.         if(dt[b] + w == dt[a] && czy[a] == 1 && czy[b] == 1){
  94.             graf3[b].push_back(a);
  95.             stopien2[a]++;
  96.         }
  97.  
  98.     }
  99.  
  100.     queue<int> q;
  101.     for(int i = 1; i <= n; i++){
  102.         if(czy[i] == 1 && stopien1[i] == 0){
  103.             q.push(i);
  104.         }
  105.     }
  106.  
  107.     while(!q.empty()){
  108.         int x = q.front(); q.pop();
  109.         topo1.push_back(x);
  110.  
  111.         for(int y : graf2[x]){
  112.             stopien1[y]--;
  113.             if(stopien1[y] == 0){
  114.                 q.push(y);
  115.             }
  116.         }
  117.     }
  118.  
  119.     vector<ll> dp1(n + 1, INF), dp2(n + 1, INF);
  120.     for(int i : topo1){
  121.         dp1[i] = du[i];
  122.     }
  123.  
  124.     for(int i : topo1){
  125.         for(int j : graf2[i]){
  126.             if(dp1[j] > dp1[i]) dp1[j] = dp1[i];
  127.         }
  128.     }
  129.  
  130.     for(int i = 1; i <= n; i++){
  131.         if(czy[i] == 1 && stopien2[i] == 0){
  132.             q.push(i);
  133.         }
  134.     }
  135.  
  136.     while(!q.empty()){
  137.         int x = q.front(); q.pop();
  138.         topo2.push_back(x);
  139.  
  140.         for(int y : graf3[x]){
  141.             stopien2[y]--;
  142.             if(stopien2[y] == 0){
  143.                 q.push(y);
  144.             }
  145.         }
  146.     }
  147.  
  148.     for(int i : topo2){
  149.         dp2[i] = du[i];
  150.     }
  151.  
  152.     for(int i : topo2){
  153.         for(int j : graf3[i]){
  154.             if(dp2[j] > dp2[i]) dp2[j] = dp2[i];
  155.         }
  156.     }
  157.  
  158.     ll ans = du[v];
  159.     for(int x : topo1){
  160.         ans = min(ans, min(dp1[x] + dv[x], dp2[x] + dv[x]));
  161.     }
  162.     cout << ans;
  163.  
  164.  
  165.     return 0;
  166. }
  167.  
Success #stdin #stdout 0.01s 8964KB
comments (?)
stdin
copy 
4 3
2 4
1 3
1 2 1
2 3 1
3 4 10
stdout
copy 
1
https://ideone.com/TfYAiH
language:
C++ (gcc 8.3)
created:
1 day 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!