BGP chọn tuyến tốt nhất theo nhiều thuộc tính; ở bài này chỉ xét độ dài AS-path (số AS trên đường) — càng ngắn càng tốt.
Cho k tuyến quảng bá tới cùng một prefix. Chọn tuyến có AS-path ngắn nhất. Tie-break: (1) AS-path nhỏ hơn theo thứ tự từ điển, (2) route_id nhỏ hơn.
Input:
3
10 3 100 200 300
20 2 100 400
30 2 100 500
Output:
20
Dòng 1: k.
k dòng: rid L a1 a2 ... aL — id tuyến, độ dài AS-path, rồi L số hiệu AS.
1 ≤ k ≤ 10^4, 1 ≤ L ≤ 50
route_id của tuyến được chọn.
Ví dụ:
Đầu vào:
3
10 3 100 200 300
20 2 100 400
30 2 100 500
Đầu ra:
20
Giải thích:
Đang tải editor...