Khi chi phí một liên kết thay đổi (ví dụ do đo lại tải), router phải tính lại đường ngắn nhất.
Cho đồ thị vô hướng, nguồn s, đích t, và một cập nhật: liên kết (u, v) đổi chi phí thành neww (liên kết này chắc chắn tồn tại). Hãy áp dụng cập nhật rồi in chi phí ngắn nhất mới từ s tới t, hoặc -1.
Input:
4 4
1 2 1
2 4 1
1 3 1
3 4 1
1 4
2 4 10
Output:
2
Dòng 1: n m.
m dòng: u v w.
Dòng kế: s t.
Dòng cuối: u v neww — cập nhật chi phí liên kết (u,v).
1 ≤ n ≤ 10^5, 1 ≤ w, neww ≤ 10^4
Chi phí ngắn nhất mới từ s tới t, hoặc -1.
Ví dụ:
Đầu vào:
4 4
1 2 1
2 4 1
1 3 1
3 4 1
1 4
2 4 10
Đầu ra:
2
Giải thích:
Đang tải editor...