fork download 
  1. // TranThienPhuc2657
  2. // 2 ngay truoc khi toi ki thi Hoc sinh gioi quoc gia 2025 - 2026, 25/12/2025.
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. #define file "TASK"
  6. #define TIME 1.0 * clock() / CLOCKS_PER_SEC
  7. #define ll long long
  8. #define pb push_back
  9. #define fi first
  10. #define se second
  11. #define pii pair <int, int>
  12. #define pll pair <ll, ll>
  13. #define Sz(x) ((int) (x).size())
  14. #define getBit(mask, i) (((mask) >> (i)) & 1)
  15. template <typename T1, typename T2> bool mini(T1 &A, T2 B) {if (A > B) A = B; else return 0; return 1;}
  16. template <typename T1, typename T2> bool maxi(T1 &A, T2 B) {if (A < B) A = B; else return 0; return 1;}
  17. const int inf = 2e9 + 7;
  18. const ll linf = 1e18l + 7;
  19. const int mod = 1e9 + 7;
  20. const int N = 1e5 + 5;
  21.  
  22. int n, m, A, B, C, D;
  23. struct Edge {
  24.     int u, v, w;
  25.  
  26.     int other(int x) {
  27.         return u ^ v ^ x;
  28.     }
  29. };
  30. vector <Edge> edges;
  31. vector <int> adj[N];
  32. ll dA[N], dB[N];
  33. ll d[4][N];
  34.  
  35. struct Dijkstra_state {
  36.     int ty, u;
  37.     ll du;
  38.  
  39.     bool operator < (const Dijkstra_state &ot) const {
  40.         return du > ot.du;
  41.     }
  42. };
  43.  
  44. ll res = linf;
  45.  
  46. // inp
  47. void inp() {
  48.     cin >> n >> m;
  49.     cin >> A >> B >> C >> D;
  50.  
  51.     edges.pb({0, 0, 0});
  52.     for (int i = 1; i <= m; i++) {
  53.         int u, v, w; cin >> u >> v >> w;
  54.         edges.pb({u, v, w});
  55.         adj[u].pb(i);
  56.         adj[v].pb(i);
  57.     }
  58. }
  59.  
  60. // init
  61. void init() {
  62.  
  63. }
  64.  
  65. // proc
  66. bool inSP(int u, int v, int w) {
  67.     return ((dA[u] + w) == dA[v] and (dA[u] + dB[v] + w) == dA[B]);
  68. }
  69.  
  70. void dijkstra(int s, ll d[]) {
  71.     for (int u = 1; u <= n; u++) d[u] = linf;
  72.     priority_queue <pll, vector <pll>, greater <pll>> pq;
  73.     d[s] = 0; pq.push({d[s], s});
  74.  
  75.     while (!pq.empty()) {
  76.         int u = pq.top().se; ll du = pq.top().fi; pq.pop();
  77.         if (du > d[u]) continue;
  78.         for (int idE: adj[u]) {
  79.             int v = edges[idE].other(u), w = edges[idE].w;
  80.             if (mini(d[v], d[u] + w)) pq.push({d[v], v});
  81.         }
  82.     }
  83. }
  84.  
  85. void dijkstra2(int s) {
  86.     for (int u = 1; u <= n; u++) d[0][u] = d[1][u] = d[2][u] = linf;
  87.     priority_queue <Dijkstra_state> pq;
  88.     d[0][s] = 0; pq.push({0, s, d[0][s]});
  89.  
  90.     while (!pq.empty()) {
  91.         int ty = pq.top().ty, u = pq.top().u; ll du = pq.top().du; pq.pop();
  92.         if (du > d[ty][u]) continue;
  93.         for (int idE: adj[u]) {
  94.             int v = edges[idE].other(u), w = edges[idE].w;
  95.  
  96.             if (ty == 0) {
  97.                 if (mini(d[0][v], d[0][u] + w)) pq.push({0, v, d[0][v]});
  98.                 if (inSP(u, v, w) and mini(d[1][v], d[0][u])) pq.push({1, v, d[1][v]});
  99.             }
  100.             else if (ty == 1) {
  101.                 if (inSP(u, v, w) and mini(d[1][v], d[1][u])) pq.push({1, v, d[1][v]});
  102.                 if (mini(d[2][v], d[1][u] + w)) pq.push({2, v, d[2][v]});
  103.             }
  104.             else {
  105.                 if (mini(d[2][v], d[2][u] + w)) pq.push({2, v, d[2][v]});
  106.             }
  107.         }
  108.     }
  109. }
  110.  
  111. void proc() {
  112.     dijkstra(A, dA);
  113.     dijkstra(B, dB);
  114.  
  115.     dijkstra2(C);
  116.     mini(res, min({d[0][D], d[1][D], d[2][D]}));
  117.  
  118.     dijkstra2(D);
  119.     mini(res, min({d[0][C], d[1][C], d[2][C]}));
  120.  
  121.     cout << res;
  122. }
  123.  
  124. signed main() {
  125.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  126.     if (fopen(file".inp", "r")) {
  127.         freopen(file".inp", "r", stdin);
  128.         freopen(file".out", "w", stdout);
  129.     }
  130.  
  131.     inp();
  132.     init();
  133.     proc();
  134.     cerr << "Time elapsed: " << TIME << "s.\n";
  135.     return 0;
  136. }
  137.  
Success #stdin #stdout #stderr 0.01s 7784KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
Time elapsed: 0.007014s.
https://ideone.com/8BF0gm
language:
C++14 (clang 8.0)
created:
1 day 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!