Một router me nhận vector khoảng cách quảng bá từ k láng giềng. Với mỗi láng giềng biết chi phí liên kết trực tiếp và bảng khoảng cách của nó tới mọi đích, router me cập nhật bảng của mình theo Bellman-Ford:
D(me, dest) = min qua các láng giềng nb của [ cost(me,nb) + D(nb, dest) ]
Khoảng cách tới chính me là 0. Giá trị 16 nghĩa là vô cực (không tới được). Tie-break next-hop: chọn láng giềng có id nhỏ nhất.
Input:
4 1 2
2 1 1 0 1 5
3 2 1 3 0 1
Output:
1 0 1
2 1 2
3 2 2
4 3 3
Dòng 1: n me k — số đích (1..n), id của router này, số láng giềng.
k dòng: nid cost d1 d2 ... dn — id láng giềng, chi phí liên kết tới nó, và n khoảng cách nó quảng bá tới đích 1..n (16 = vô cực).
1 ≤ n ≤ 500, 1 ≤ k ≤ n, chi phí liên kết ≥ 1
n dòng: dest dist nexthop. Với dest = me in me 0 me. Đích không tới được in dest 16 -1.
Ví dụ:
Đầu vào:
4 1 2
2 1 1 0 1 5
3 2 1 3 0 1
Đầu ra:
1 0 1
2 1 2
3 2 2
4 3 3
Giải thích:
Đang tải editor...