ECMP (Equal-Cost Multi-Path) cho phép chia tải trên nhiều đường có cùng chi phí ngắn nhất. Từ router s tới đích t, một láng giềng v của s là next-hop hợp lệ nếu w(s,v) + dist(v,t) = dist(s,t).
Hãy liệt kê các next-hop ECMP từ s (các đỉnh láng giềng nằm trên đường ngắn nhất), theo thứ tự tăng dần. Nếu t không tới được, in -1.
Gợi ý: chạy Dijkstra từ t để có dist(·, t).
Input:
4 4
1 2 1
1 3 1
2 4 1
3 4 1
1 4
Output:
2 3
Dòng 1: n m (đồ thị vô hướng).
m dòng: u v w.
Dòng cuối: s t (s ≠ t).
1 ≤ n ≤ 10^5, 1 ≤ w ≤ 10^4
Danh sách id next-hop tăng dần, cách nhau dấu cách; hoặc -1.
Ví dụ:
Đầu vào:
4 4
1 2 1
1 3 1
2 4 1
3 4 1
1 4
Đầu ra:
2 3
Giải thích:
Đang tải editor...