Cho một mạng vô hướng có trọng số (độ trễ liên kết), hãy dùng Dijkstra từ nút nguồn src để dựng bảng định tuyến đầy đủ: với mỗi đích, cho biết next-hop (nút kế tiếp trên đường đi ngắn nhất) và tổng chi phí.
Quy tắc chọn đường khi hòa chi phí: chọn next-hop có chỉ số nhỏ hơn. Nếu đích không tới được, in dest - -.
In các đích theo thứ tự chỉ số tăng dần (bỏ qua chính src), mỗi dòng dest nexthop cost. Chỉ dùng thư viện chuẩn (heapq).
Đồ thị 3 nút 0-1 (cost 1), 1-2 (cost 1), src=0: tới 1 next-hop 1 cost 1; tới 2 next-hop 1 cost 2.
Dòng đầu n m src. m dòng sau: u v w (liên kết vô hướng, trọng số w).
1 ≤ n ≤ 1000. 0 ≤ m ≤ 5000. 1 ≤ w ≤ 1000. 0 ≤ u,v,src < n.
In n-1 dòng (mọi đích ≠ src) theo chỉ số tăng: dest nexthop cost, hoặc dest - - nếu không tới được.
Ví dụ:
Đầu vào:
3 2 0
0 1 1
1 2 1
Đầu ra:
1 1 1
2 1 2
Giải thích:
Đang tải editor...