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: