Để tăng độ tin cậy, mạng cần tính đường dự phòng không dùng một liên kết cụ thể (giả định liên kết đó có thể hỏng).
Cho đồ thị vô hướng, nguồn s, đích t, và một liên kết (fu, fv). Hãy in hai giá trị:
primary: chi phí ngắn nhất từ s tới t trên đồ thị đầy đủ.backup: chi phí ngắn nhất khi loại bỏ liên kết (fu, fv).Mỗi giá trị là -1 nếu không tồn tại đường tương ứng.
Input:
4 4
1 2 1
2 4 1
1 3 5
3 4 5
1 4
2 4
Output:
2 10
Dòng 1: n m.
m dòng: u v w.
Dòng kế: s t.
Dòng cuối: fu fv — liên kết cần tránh ở đường dự phòng.
1 ≤ n ≤ 10^5, 1 ≤ w ≤ 10^4
primary backup.
Ví dụ:
Đầu vào:
4 4
1 2 1
2 4 1
1 3 5
3 4 5
1 4
2 4
Đầu ra:
2 10
Giải thích:
Đang tải editor...