Khi topo thay đổi, router nguồn phát LSA và thông tin lan truyền (flooding) khắp mạng theo các liên kết, mỗi liên kết có độ trễ riêng. Thời gian hội tụ là thời điểm router cuối cùng nhận được LSA — tức max của độ trễ đường ngắn nhất (theo độ trễ) từ nguồn tới mọi router tới được.
Cho đồ thị vô hướng với độ trễ trên cạnh và router nguồn src, hãy tính thời gian hội tụ (bỏ qua router không tới được).
Input:
4 4 1
1 2 2
2 3 2
1 3 5
3 4 1
Output:
5
Dòng 1: n m src.
m dòng: u v delay (vô hướng).
1 ≤ n ≤ 10^5, 1 ≤ delay ≤ 10^4
Một số nguyên: thời gian hội tụ (độ trễ lớn nhất trong các đường ngắn nhất từ src).
Ví dụ:
Đầu vào:
4 4 1
1 2 2
2 3 2
1 3 5
3 4 1
Đầu ra:
5
Giải thích:
Đang tải editor...