Bài tập | NEU OJ

STP bầu root bridge là switch có Bridge ID nhỏ nhất. Sau đó mỗi bridge tính Root Path Cost — tổng chi phí đường ngắn nhất về root bridge.

Cho n bridge (mỗi bridge có một Bridge ID) và m liên kết (theo chỉ số bridge 1..n) có chi phí, hãy:

In Bridge ID của root (nhỏ nhất).
In n dòng BridgeID RootPathCost, sắp xếp theo Bridge ID tăng dần. Bridge không nối tới root có chi phí -1.

Ví dụ

Input:

3 3
32771 32769 32770
1 2 4
2 3 3
1 3 10

Output:

Định dạng đầu vào:
Dòng 1: n m. Dòng 2: n số — Bridge ID của bridge 1..n (phân biệt). m dòng: i j cost — liên kết giữa bridge chỉ số i và j.
Ràng buộc đầu vào:
1 ≤ n ≤ 10^4, 1 ≤ cost ≤ 10^4
Định dạng đầu ra:
Dòng 1: Bridge ID của root. Sau đó n dòng BridgeID RootPathCost (theo Bridge ID tăng dần).

solution

Đề bài: [Mạng máy tính] STP: Root bridge và chi phí đường về gốc

Ví dụ