Bình luận

• 
  

  1

  

  TranThienPhuc2657  đã bình luận lúc 26, Tháng 1, 2026, 13:56

  Quan điểm cá nhân về đề bài sau khi đã AC bài: Theo mình nghĩ là đề chưa được tường minh về việc đường đi ngắn của Hasun, mình nghĩ đề nên nói rõ hơn là các đường hầm trên đường đi ngắn nhất từ ~A~ tới ~B~ và theo đúng chiều từ ~A~ tới ~B~ đã được kích hoạt và Hasun sẽ đi từ ~C~ tới ~D~ hoặc từ ~D~ tới ~C~ sao cho ngắn nhất. Bởi vì mình làm theo kiểu này mới AC được bài.

• 
  

  3

  

  quannm  đã bình luận lúc 27, Tháng 12, 2025, 15:23

  Ai có solution bài này cho em tham khảo với

• 
  

  5

  

  TranThienPhuc2657  đã bình luận lúc 27, Tháng 12, 2025, 15:49 ← sửa 21 →

  Comment này spoil thuật

  - - Các bạn chỉ nên dùng code của mình để tham khảo cách cài đặt chứ không phải là copy cho có AC nhé, làm như vậy sẽ không có ý nghĩa gì.

  ---

  Lời giải

  • Đầu tiên bạn Dijkstra ~A~ và ~B~ để có thể xác định các cạnh nào thuộc đường đi ngắn nhất của Aaron.

  • Sau đó bạn Dijkstra Hasun, mình có sử dụng ~1~ nhận xét là: hai đường đi ngắn nhất chỉ giao nhau tại ~1~ đoạn liên tiếp.

    • Khi này mình sẽ có thể thêm chiều hai cho Dijkstra biểu diễn trạng thái chưa giao, đang giao và đã giao giữa đường đi của Hasun với đường đi ngắn nhất của Aaron (Hướng tiếp cận 1)
    • Hoặc là bạn có thể build 1 cái ~DAG~, chuẩn bị thêm Dijkstra ~C~ và ~D~ và ~DP~ cái nửa phần đầu lúc mà đi từ tới rồi cộng thêm phần đi từ điểm tới đích để ra toàn bộ đường đi (chi tiết hơn ở dưới phần Code tham khảo) (Hướng tiếp cận 2).
    • Thực ra thì hai hướng tiếp cận này là cùng một ý tưởng nhưng mà cách triển khai khác nhau.

  Lưu ý

  1. Dijkstra Hasun ở đây là mình Dijkstra cả ~C~ và ~D~ và lấy ~\min~ (về lí do mình không hiểu tại sao làm như thế này mới đúng mà không phải Dijkstra ~1~ đỉnh là đã đủ đúng, cái này mình xin nhường lại cho các bạn khác giải thích giúp mình).

  2. Khi Dijkstra Hasun thì cái cạnh mình xét nó phải nằm trong đường đi ngắn nhất từ ~A~ tới ~B~ và phải đúng về chiều đi khớp với chiều đi từ ~A~ tới ~B~ nữa. Cụ thể hơn thì nếu cạnh ~(E, F)~ nằm trong đường đi ngắn nhất từ ~(A, B)~ thì cạnh này thỏa nhưng điều này không có nghĩa là cạnh ~(F, E)~ sẽ thỏa. Nếu mà xét cạnh mà cho nó thỏa khi một trong hai chiều của cạnh thuộc đường đi ngắn nhất từ ~A~ đến ~B~ thì cái đường đi ~C~ đến ~D~ nó sẽ sai theo ý của đề bài.

  • Quan điểm cá nhân: Cái này theo mình nghĩ là đề chưa được tường minh về việc này, mình nghĩ đề nên nói rõ hơn là các đường hầm trên đường đi ngắn nhất từ ~A~ tới ~B~ và theo đúng chiều từ ~A~ tới ~B~ đã được kích hoạt và Hasun sẽ đi từ ~C~ tới ~D~ hoặc từ ~D~ tới ~C~ sao cho ngắn nhất.

  • Cập nhập về lí do tại sao phải Dijkstra cả hai đỉnh ~C~ và ~D~ (Credit: dex111222333444555, comment ở ngay dưới comment này VNOJ): Khi Dijkstra ~A~ đến ~B~, tập cạnh thỏa mãn thuộc đường đi ngắn nhất sẽ tạo thành một cái ~DAG~ gồm các cạnh có hướng, do cái việc có hướng này nên khi Dijkstra ~C~ tới ~D~ thì chỉ có thể nhận được một số phần cạnh trong tất cả các cạnh thỏa mãn chứ không có nhận hết, tương tự với chiều ngược lại từ ~D~ về ~C~. Do đó ta cần phải Dijkstra từ cả hai đầu để đảm bảo tính đúng đắn.

  • Ví dụ như sau:

    • Aaron: ~A \rightarrow E \rightarrow F \rightarrow B~

    • Hasun: ~C \rightarrow F \rightarrow E \rightarrow D~

    • Khi mà chỉ Dijkstra từ ~C~ tới ~D~ thì ta không thể nhận cạnh ~(F, E)~ được do cạnh này không thuộc đường đi ngắn nhất từ ~A~ tới ~B~, nhưng xét theo chiều ngược lại, khi Dijkstra từ ~D~ về ~C~ thì cạnh ~(E, F)~ lại thuộc đường đi ngắn nhất từ ~A~ tới ~B~ nên là nó nhận cạnh này.

  ---

  Code tham khảo

  • Hướng tiếp cận 1

  // TranThienPhuc2657
  // 2 ngay truoc khi toi ki thi Hoc sinh gioi quoc gia 2025 - 2026, 25/12/2025.
  #include <bits/stdc++.h>
  using namespace std;
  #define file "TASK"
  #define TIME 1.0 * clock() / CLOCKS_PER_SEC
  #define ll long long
  #define pb push_back
  #define fi first
  #define se second
  #define pii pair <int, int>
  #define pll pair <ll, ll>
  #define Sz(x) ((int) (x).size())
  #define getBit(mask, i) (((mask) >> (i)) & 1)
  template <typename T1, typename T2> bool mini(T1 &A, T2 B) {if (A > B) A = B; else return 0; return 1;}
  template <typename T1, typename T2> bool maxi(T1 &A, T2 B) {if (A < B) A = B; else return 0; return 1;}
  const int inf = 2e9 + 7;
  const ll linf = 1e18l + 7;
  const int mod = 1e9 + 7;
  const int N = 1e5 + 5;
  
  int n, m, A, B, C, D;
  struct Edge {
      int u, v, w;
  
      int other(int x) {
          return u ^ v ^ x;
      }
  };
  vector <Edge> edges;
  vector <int> adj[N];
  ll dA[N], dB[N];
  ll d[4][N];
  
  struct Dijkstra_state {
      int ty, u;
      ll du;
  
      bool operator < (const Dijkstra_state &ot) const {
          return du > ot.du;
      }
  };
  
  ll res = linf;
  
  // inp
  void inp() {
      cin >> n >> m;
      cin >> A >> B >> C >> D;
  
      edges.pb({0, 0, 0});
      for (int i = 1; i <= m; i++) {
          int u, v, w; cin >> u >> v >> w;
          edges.pb({u, v, w});
          adj[u].pb(i);
          adj[v].pb(i);
      }
  }
  
  // init
  void init() {
  
  }
  
  // proc
  bool inSP(int u, int v, int w) {
      return ((dA[u] + w) == dA[v] and (dA[u] + dB[v] + w) == dA[B]);
  }
  
  void dijkstra(int s, ll d[]) {
      for (int u = 1; u <= n; u++) d[u] = linf;
      priority_queue <pll, vector <pll>, greater <pll>> pq;
      d[s] = 0; pq.push({d[s], s});
  
      while (!pq.empty()) {
          int u = pq.top().se; ll du = pq.top().fi; pq.pop();
          if (du > d[u]) continue;
          for (int idE: adj[u]) {
              int v = edges[idE].other(u), w = edges[idE].w;
              if (mini(d[v], d[u] + w)) pq.push({d[v], v});
          }
      }
  }
  
  ll dijkstra2(int s, int t) {
      for (int u = 1; u <= n; u++) d[0][u] = d[1][u] = d[2][u] = linf;
      priority_queue <Dijkstra_state> pq;
      d[0][s] = 0; pq.push({0, s, d[0][s]});
  
      while (!pq.empty()) {
          int ty = pq.top().ty, u = pq.top().u; ll du = pq.top().du; pq.pop();
          if (du > d[ty][u]) continue;
          for (int idE: adj[u]) {
              int v = edges[idE].other(u), w = edges[idE].w;
  
              if (ty == 0) {
                  if (mini(d[0][v], d[0][u] + w)) pq.push({0, v, d[0][v]});
                  if (inSP(u, v, w) and mini(d[1][v], d[0][u])) pq.push({1, v, d[1][v]});
              }
              else if (ty == 1) {
                  if (inSP(u, v, w) and mini(d[1][v], d[1][u])) pq.push({1, v, d[1][v]});
                  if (mini(d[2][v], d[1][u] + w)) pq.push({2, v, d[2][v]});
              }
              else {
                  if (mini(d[2][v], d[2][u] + w)) pq.push({2, v, d[2][v]});
              }
          }
      }
  
      return min({d[0][t], d[1][t], d[2][t]});
  }
  
  void proc() {
      dijkstra(A, dA);
      dijkstra(B, dB);
      cout << min(dijkstra2(C, D), dijkstra2(D, C));
  }
  
  signed main() {
      ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
      if (fopen(file".inp", "r")) {
          freopen(file".inp", "r", stdin);
          freopen(file".out", "w", stdout);
      }
  
      inp();
      init();
      proc();
      cerr << "Time elapsed: " << TIME << "s.\n";
      return 0;
  }
  

  • Hướng tiếp cận 2

  ideone

• 
  

  2

  

  dex111222333444555  đã bình luận lúc 16, Tháng 1, 2026, 9:49 ← sửa 8 →

  Trả lời lý do 1 đỉnh từ C đến D chưa đủ vì đồ thì mới mình tạo ra nó là DAG nên là đồ thị vô hướng sẽ có trường hợp mà đường đi từ U -> V trùng với đường đi từ S -> T một đoạn nhưng đoạn S -> T nó có cạnh ngược với đường đi từ U -> V.

  Ví dụ một case cho dễ hiểu:

  A -> E -> F -> B và C -> F -> E -> D. Vì đồ thị anh tạo là DAG nên nó chỉ có cạnh E -> F chứ không có cạnh B -> A nên phải có trường hợp F -> E nữa mới AC

• 
  

  2

  

  TranThienPhuc2657  đã bình luận lúc 18, Tháng 1, 2026, 1:48

  Cảm ơn em nhé!

• 
  

  -1

  

  d1codce  đã bình luận lúc 7, Tháng 1, 2026, 13:36 ← sửa 2 →

  orz