fork download
copy 
  1. #include <bits/stdc++.h> // NeOWami
  2. using namespace std;
  3.  
  4. #define ft first
  5. #define sc second
  6. #define int long long
  7. using pii = pair<int, int>;
  8. template<class T> using heapmin = priority_queue<T, vector<T>, greater<T>>;
  9.  
  10. const int N = 2e5 + 5;
  11. const int inf = 1e18;
  12. int n, m;
  13. int S, T, U, V;
  14.  
  15. struct Edge {
  16.     int u, v, w;
  17. } E[N];
  18. vector<pii> G[N];
  19.  
  20. bool ckmin(int &u, int v) {
  21.     if (u > v) return u = v, 1;
  22.     return 0;
  23. }
  24.  
  25.  
  26. namespace subfull {
  27. int distS[N], distT[N], distV[N], distU[N];
  28. int candE[N];
  29. vector<pii> g[N];
  30.  
  31. void calc(int root, int dist[], vector<pii> G[]) {
  32.     heapmin<pii> Q;
  33.     for (int i = 1; i <= n; i++) dist[i] = inf;
  34.     dist[root] = 0;
  35.     Q.push({0, root});
  36.     while(!Q.empty()) {
  37.         int u = Q.top().sc, old = Q.top().ft;
  38.         Q.pop();
  39.         if (old != dist[u]) continue;
  40.         for (pii item: G[u]) {
  41.             int v = item.ft, w = item.sc;
  42.             if (ckmin(dist[v], w + dist[u])) {
  43.                 Q.push({dist[v], v});
  44.             }
  45.         }
  46.     }
  47. }
  48.  
  49. int getMinU() {
  50.     for (int i = 1; i <= n; i++) g[i].clear();
  51.     for (int i = 1; i <= m; i++) {
  52.         int u = E[i].u, v = E[i].v, w = E[i].w;
  53.         if (candE[i] == 0) {
  54.             g[u].push_back({v, w});
  55.             g[v].push_back({u, w});
  56.         }
  57.         if (candE[i] == 1) {
  58.             g[u].push_back({v, 0});
  59.         }
  60.         if (candE[i] == 2) {
  61.             g[v].push_back({u, 0});
  62.         }
  63.     }
  64.     calc(U, distU, g);
  65.     int mmin = inf;
  66.     for (int mid = 1; mid <= n; mid++) mmin = min(mmin, distU[mid] + distV[mid]);
  67.     return mmin;
  68. }
  69.  
  70. void solve() {
  71.     calc(S, distS, G);
  72.     calc(T, distT, G);
  73.     calc(V, distV, G);
  74.     fill(candE + 1, candE + m + 1, 0);
  75.     int ans = distV[U];
  76.     for (int i = 1; i <= m; i++) {
  77.         int u = E[i].u, v = E[i].v, w = E[i].w;
  78.         if (distS[u] + w + distT[v] == distS[T]) candE[i] = 1;
  79.         if (distS[v] + w + distT[u] == distS[T]) candE[i] = 2;
  80.     }
  81.     ans = min(ans, getMinU());
  82.     for (int i = 1; i <= m; i++) {
  83.         if (candE[i] == 2) candE[i] = 1;
  84.         else if (candE[i] == 1) candE[i] = 2;
  85.     }
  86.     ans = min(ans, getMinU());
  87.     cout << ans;
  88. }
  89. };
  90.  
  91. signed main() {
  92.     cin.tie(NULL)->sync_with_stdio(false);
  93.     if(ifstream("PATH.inp")) {
  94.         freopen("PATH.inp", "r", stdin);
  95.         freopen("PATH.out", "w", stdout);
  96.     }
  97.     cin >> n >> m >> S >> T >> U >> V;
  98.     for (int i = 1; i <= m; i++) {
  99.         int u, v, w; cin >> u >> v >> w;
  100.         E[i] = {u, v, w};
  101.         G[u].push_back({v, w});
  102.         G[v].push_back({u, w});
  103.     }
  104.     return subfull::solve(), 0;
  105.     return 0;
  106. }
Success #stdin #stdout 0.01s 21492KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/eCf7tf
language:
C++14 (gcc 8.3)
created:
5 days 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!