fork download
copy 
  1. // TranThienPhuc2657
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define file "TASK"
  5. #define TIME 1.0 * clock() / CLOCKS_PER_SEC
  6. #define ll long long
  7. #define pb push_back
  8. #define fi first
  9. #define se second
  10. #define pii pair <int, int>
  11. #define pll pair <ll, ll>
  12. #define Sz(x) ((int) (x).size())
  13. #define getBit(mask, i) (((mask) >> (i)) & 1)
  14. template <typename T1, typename T2> bool mini(T1 &A, T2 B) {if (A > B) A = B; else return 0; return 1;}
  15. template <typename T1, typename T2> bool maxi(T1 &A, T2 B) {if (A < B) A = B; else return 0; return 1;}
  16. const int inf = 2e9 + 7;
  17. const ll linf = 1e18l + 7;
  18. const int mod = 1e9 + 7;
  19. const int N = 2e5 + 5;
  20.  
  21. int n, m, A, B, C, D;
  22. vector <pii> adj[N];
  23. vector <int> nadj[N];
  24. ll dA[N], dB[N], dC[N], dD[N];
  25. int in[N];
  26. ll dpC[N], dpD[N];
  27. ll res = linf;
  28.  
  29. // inp
  30. void inp() {
  31.     cin >> n >> m >> A >> B >> C >> D;
  32.     for (int i = 1; i <= m; i++) {
  33.         int u, v, w; cin >> u >> v >> w;
  34.         adj[u].pb({v, w});
  35.         adj[v].pb({u, w});
  36.     }
  37. }
  38.  
  39. // init
  40. void dijkstra(ll *d, const int &s) {
  41.     for (int u = 1; u <= n; u++) d[u] = linf;
  42.     priority_queue <pll, vector <pll>, greater <pll>> pq;
  43.     d[s] = 0;
  44.     pq.push({0, s});
  45.  
  46.     while (!pq.empty()) {
  47.         ll du = pq.top().fi, u = pq.top().se; pq.pop();
  48.         if (du > d[u]) continue;
  49.         for (pii e: adj[u]) {
  50.             int v = e.fi, w = e.se;
  51.             if (mini(d[v], d[u] + w)) pq.push({d[v], v});
  52.         }
  53.     }
  54. }
  55.  
  56. bool inSP(int u, int v, int w) {
  57.     return dA[u] + w == dA[v] and dA[u] + w + dB[v] == dA[B];
  58. }
  59.  
  60. void init() {
  61.     dijkstra(dA, A); dijkstra(dB, B); dijkstra(dC, C); dijkstra(dD, D);
  62.  
  63.     for (int u = 1; u <= n; u++) {
  64.         for (pii e: adj[u]) {
  65.             int v = e.fi, w = e.se;
  66.             if (inSP(u, v, w)) {
  67.                 nadj[u].pb(v);
  68.                 in[v]++;
  69.             }
  70.         }
  71.     }
  72. }
  73.  
  74. // proc
  75. void proc() {
  76.     for (int u = 1; u <= n; u++) dpC[u] = dpD[u] = linf;
  77.     queue <int> q;
  78.     for (int u = 1; u <= n; u++) if (!in[u]) q.push(u);
  79.     while (!q.empty()) {
  80.         int u = q.front(); q.pop();
  81.  
  82.         mini(dpC[u], dC[u]);
  83.         mini(dpD[u], dD[u]);
  84.  
  85.         mini(res, dpC[u] + dD[u]);
  86.         mini(res, dpD[u] + dC[u]);
  87.  
  88.         for (int v: nadj[u]) {
  89.             mini(dpC[v], dpC[u]);
  90.             mini(dpD[v], dpD[u]);
  91.  
  92.             if (--in[v] == 0) q.push(v);
  93.         }
  94.     }
  95.  
  96.     cout << res;
  97. }
  98.  
  99. signed main() {
  100.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  101.     if (fopen(file".inp", "r")) {
  102.         freopen(file".inp", "r", stdin);
  103.         freopen(file".out", "w", stdout);
  104.     }
  105.  
  106.     inp();
  107.     init();
  108.     proc();
  109.     cerr << "Time elapsed: " << TIME << "s.\n";
  110.     return 0;
  111. }
  112.  
  113.  
Success #stdin #stdout #stderr 0.01s 17944KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000000000000007
stderr
copy 
Time elapsed: 0.008643s.
https://ideone.com/Vkyja6
language:
C++14 (clang 8.0)
created:
10 days ago
visibility:
secret

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!