Mở rộng bài Dijkstra: ngoài chi phí, hãy liệt kê dãy router trên đường ngắn nhất từ s tới t.
Khi có nhiều đường cùng chi phí, tie-break: chọn đỉnh liền trước (predecessor) có chỉ số nhỏ nhất (cập nhật predecessor khi gặp chi phí bằng nhau nhưng đỉnh trước nhỏ hơn). Nếu không có đường, in -1.
Input:
4 4
1 2 1
2 4 5
1 3 2
3 4 1
1 4
Output:
1 3 4
Dòng 1: n m.
m dòng: u v w (vô hướng).
Dòng cuối: s t.
1 ≤ n ≤ 10^5, 0 ≤ m ≤ 2·10^5, 1 ≤ w ≤ 10^4
Dãy router từ s tới t cách nhau bởi dấu cách, hoặc -1.
Ví dụ:
Đầu vào:
4 4
1 2 1
2 4 5
1 3 2
3 4 1
1 4
Đầu ra:
1 3 4
Giải thích:
Đang tải editor...