Bình luận

• 
  

  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

• 
  

  4

  

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

  Comment này spoil thuật

  • Đầ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.

  • Lưu ý: 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).

  • Lưu ý 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:

  // 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});
         }
     }
  }
  
  void dijkstra2(int s) {
     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]});
             }
         }
     }
  }
  
  void proc() {
     dijkstra(A, dA);
     dijkstra(B, dB);
  
     dijkstra2(C);
     mini(res, min({d[0][D], d[1][D], d[2][D]}));
  
     dijkstra2(D);
     mini(res, min({d[0][C], d[1][C], d[2][C]}));
  
     cout << res;
  }
  
  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;
  }
  

  • Hoặc có một hướng tiếp cận khác cho việc tìm đường đi ngắn nhất từ ~C~ tới ~D~ như sau: đồ thị các cạnh thuộc đường đi ngắn nhất từ ~A~ tới ~B~ là một cái ~DAG~, khi này, ta build cái đồ thị ảo ~DAG~ rồi ta có thể DP từ ~C~ và DP từ ~D~ trong độ phức tạp ~\mathcal{O}(n)~ đối với riêng thao tác này, tối ưu hơn cách trên của mình.

• 
  

  2

  

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

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

• 
  

  0

  

  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