Mô tả và yêu cầu

MẠNG GIAO THÔNG
Theo thiết kế, một mạng giao thông gồm N nút có tên từ 1 đến N. Chi phí để xây dựng
đường hai chiều trực tiếp từ nút i đến nút j bằng A[i,j] = A[j,i], với mọi i, A[i,i] = 0. Hai
tuyến đường khác nhau không cắt nhau tại điểm không là đầu mút. Hiện tại đã xây dựng
được K tuyến đường.
Yêu cầu: Hãy cho biết đã xây dựng đã bảo đảm sự đi lại giữa hai nút bất kì hay chưa? Nếu
chưa, hãy chọn một số tuyến đường cần xây dựng thêm sao cho:
1. Các tuyến đường sẽ xây dựng thêm cùng với các tuyến đường đã xây dựng trước
đó bảo đảm sự đi lại giữa hai nút bất kì.
2. Tổng kinh phí xây dựng các tuyến đường thêm là ít nhất.
Dữ liệu vào: Cho trong file traffic.inp có cấu trúc nhau sau:
• Dòng 1: ghi hai số N, K (3 ≤ N ≤ 1000; 0 ≤ K < N*N).
• Trong K dòng tiếp theo, mỗi dòng ghi hai số u, v (1 ≤ u, v ≤ N) cho biết tuyến đường
nối hai nút u và v đã xây dựng.
• N dòng cuối cùng, mỗi dòng ghi N số nguyên dương, số thứ j ở dòng thứ i là
A[i,j] (1 ≤ A[i,j] ≤ 106, i ≠ j) thể hiện chi phí xây dựng tuyến đường trực tiếp nối i
và j.
Kết quả ra: Ghi vào file traffic.out:
Dòng 1: Ghi “YES” nếu hệ thống đã xây dựng trước đó đảm bảo sự đi lại giữa hai
nút bất kì, nếu không thì ghi một số nguyên duy nhất là tổng chi phí của các tuyến
đường cần xây dựng thêm.

Ví dụ

traffic.inp                      traffic.out
                       5 4                              1
                       1 2
                       3 2
                       3 1
                       4 5
                       0 1 1 1 1
                       1 0 1 1 1
                       1 1 0 1 1
                       1 1 1 0 1
                       1 1 1 1 0