Editorial for Lối Đi Riêng


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.
  • Subtask \(1\): Gọi \(D[u][bal]\) là đường đi ngắn nhất tới đỉnh \(u\), sau khi đi trong ví còn lại số tiền là \(bal\). Mỗi khi đi đến một đỉnh \(v\) từ \(u\), ta thực hiện kiểm tra, nếu \(D[v][bal-c_{i}] > D[u][bal] + t_{i}\) thì thực hiện đi tiếp, ngoài ra sau mỗi lần đi, ta sẽ thử rút đầy tiên, bằng cách kiểm tra xem \(D[v][k] > D[v][bal-c_{i}] + 1\), nếu thỏa mãn thì coi như ta sẽ rút tiền với chi phí thời gian là \(1\) (vẫn đẩy cả trường hợp này vào priority_queue để xử lí Dijkstra).

  • Subtask \(2\): Gọi \(D[u]\) là đường đi ngắn nhất tới đỉnh \(u\), thực hiện Dijkstra như một bài Dijkstra cơ bản.

  • Subtask \(3\): Cải tiến từ subtask \(1\). Mỗi lần thử update \(D[v][bal]\), ta sẽ update cho cả các phần tử \(D[v][bal-1], D[v][bal-2],..., D[v][0]\). Do nếu có ít tiền hơn mà thời gian đi lại dài hơn so với lúc có nhiều tiền hơn mà thời gian đi ngắn hơn thì không có nghĩa lí gì, nên ta update xuống cả các phần tử bên dưới. Cụ thể các bạn có thể thử xem đoạn code ở dưới:

C++
for (int i = bal-c; i >= 0; i--)
    D[v][i] = min(D[v][i],D[u][bal] + t);


Comments

There are no comments at the moment.