Trong một mạng gồm máy tính đánh số từ đến . Sơ đồ nối mạng được cho bởi hệ thống gồm kênh nối trực tiếp giữa một số cặp máy trong mạng. Biết chi phí truyền một đơn vị thông tin theo mỗi kênh nối của mạng.
Người ta cần chuyển một bức thông điệp từ máy đến máy sao cho tổng chi phí trên đường đi là nhỏ nhất.
Yêu cầu: Hãy lập trình để giải bài toán trên.
Dữ liệu vào:
Dòng đầu tiên ghi bốn số cách nhau bởi dấu cách ;
Mỗi dòng thứ trong số dòng tiếp theo ghi thông tin về kênh nối thứ của mạng gồm số . Trong đó là chỉ số của hai máy tương ứng với kênh này và (nguyên dương và ) là chi phí để truyền một đơn vị thông tin từ máy đến máy (và ngược lại) theo kênh này .
