OSPF dùng thuật toán Dijkstra để tìm đường có tổng chi phí nhỏ nhất. Cho đồ thị vô hướng có trọng số dương (router là đỉnh, liên kết là cạnh có chi phí), hãy tìm tổng chi phí nhỏ nhất từ router nguồn s tới router đích t.
Nếu không có đường, in -1.
Thuật toán: khởi tạo dist[s]=0, dùng hàng đợi ưu tiên, mỗi lần lấy đỉnh có dist nhỏ nhất rồi nới lỏng (relax) các cạnh kề.
Input:
4 4
1 2 1
2 4 5
1 3 2
3 4 1
1 4
Output:
3
Dòng 1: n m — số router (1..n) và số liên kết.
m dòng: u v w — liên kết vô hướng giữa u và v chi phí w.
Dòng cuối: s t.
1 ≤ n ≤ 10^5, 0 ≤ m ≤ 2·10^5, 1 ≤ w ≤ 10^4
Tổng chi phí nhỏ nhất từ s tới t, hoặc -1 nếu không tới được.
Ví dụ:
Đầu vào:
4 4
1 2 1
2 4 5
1 3 2
3 4 1
1 4
Đầu ra:
3
Giải thích:
Đang tải editor...