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. int distS[N], distT[N], distV[N], distU[N];
  26. int candE[N];
  27.  
  28. void calc(int root, int dist[]) {
  29.     heapmin<pii> Q;
  30.     for (int i = 1; i <= n; i++) dist[i] = inf;
  31.     dist[root] = 0;
  32.     Q.push({0, root});
  33.     while(!Q.empty()) {
  34.         int u = Q.top().sc, old = Q.top().ft;
  35.         Q.pop();
  36.         if (old != dist[u]) continue;
  37.         for (pii item: G[u]) {
  38.             int v = item.ft, w = item.sc;
  39.             if (ckmin(dist[v], w + dist[u])) {
  40.                 Q.push({dist[v], v});
  41.             }
  42.         }
  43.     }
  44. }
  45. vector<int> tour;
  46. bool vis[N];
  47. vector<int> g[N];
  48. int dp[N];
  49.  
  50. inline void dfsGettour(int u) {
  51.     vis[u] = 1;
  52.     for (int v: g[u]) {
  53.         if (!vis[v]) {
  54.             dfsGettour(v);
  55.         }
  56.     }
  57.     tour.push_back(u);
  58. }
  59. int getMinU() {
  60.     for (int i = 1; i <= n; i++) g[i].clear();
  61.     for (int i = 1; i <= m; i++) {
  62.         int u = E[i].u, v = E[i].v, w = E[i].w;
  63.  
  64.         if (candE[i] == 1) {
  65.             g[u].push_back(v);
  66.         }
  67.         if (candE[i] == 2) {
  68.             g[v].push_back(u);
  69.         }
  70.     }
  71.     tour.clear();
  72.     for (int i = 1; i <= n; i++) vis[i] = 0;
  73.     dfsGettour(S);
  74.     int mmin = inf;
  75.     // cerr << "?";
  76.     for (int i = 1; i <= n; i++) dp[i] = inf;
  77.     for (int x: tour) {
  78.         dp[x] = distV[x];
  79.         for (int k: g[x]) {
  80.             dp[x] = min(dp[x], dp[k]);
  81.         }
  82.         mmin = min(mmin, dp[x] + distU[x]);
  83.     }
  84.     return mmin;
  85. }
  86. signed main() {
  87.     cin.tie(NULL)->sync_with_stdio(false);
  88.     if(ifstream("PATH.inp")) {
  89.         freopen("PATH.inp", "r", stdin);
  90.         freopen("PATH.out", "w", stdout);
  91.     }
  92.     cin >> n >> m >> S >> T >> U >> V;
  93.     for (int i = 1; i <= m; i++) {
  94.         int u, v, w; cin >> u >> v >> w;
  95.         E[i] = {u, v, w};
  96.         G[u].push_back({v, w});
  97.         G[v].push_back({u, w});
  98.     }
  99.     calc(S, distS);
  100.     calc(T, distT);
  101.     calc(U, distU);
  102.     calc(V, distV);
  103.     fill(candE + 1, candE + m + 1, 0);
  104.     int ans = distV[U];
  105.     for (int i = 1; i <= m; i++) {
  106.         int u = E[i].u, v = E[i].v, w = E[i].w;
  107.         if (distS[u] + w + distT[v] == distS[T]) candE[i] = 1;
  108.         if (distS[v] + w + distT[u] == distS[T]) candE[i] = 2;
  109.     }
  110.     ans = min(ans, getMinU());
  111.     swap(U, V);
  112.     swap(distU, distV);
  113.     ans = min(ans, getMinU());
  114.     cout << ans;
  115.     return 0;
  116. }
  117.  
Success #stdin #stdout 0.01s 22136KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/9agLsL
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!