Vua
Peaceful vừa khai hoang một vùng đất để lập ra nước Peace, lúc đầu chỉ có N
thành phố được đánh số từ 1 đến N và không có con đường nào
Vua
Peace chọn ra 4 thành phố đặc biệt để làm trung tâm kinh tế và 4 thành phố này
phải được liên thông với nhau. Chi phí xây dựng các con đường không phải nhỏ vì
thế mà nhà cua muốn sử dụng chi phí ít nhất để xây dựng các con đường sao cho 4
thành phố đặc biệt đó vẫn liên thông
Bạn
chỉ biết chi phí ước tính để xây dựng một số con đường và bạn hãy chọn ra một số
con đường để xây dựng theo ý muốn của nhà vua biết rằng luôn luôn tồn tại ít nhất
một phương án xây dựng sao cho 4 thành phố đặc biệt liên thông
Dữ liệu vào: từ
file QBBUILD.INP
+
Dòng đầu tiên ghi số nguyên dương N là số lượng các thành phố (4≤N≤100)
+
Dòng thứ hai ghi 4 số nguyên là số hiệu của 4 thành phố đặc biệt
+
Trong các dòng tiếp theo mỗi dòng ghi 3 số nguyên dương u, v và c với ý nghĩa
muốn xây dựng một con đường hai chiều nối trực tiếp hai thành phố u và v thì
chi phí là c (1≤c≤5000);
Dữ liệu ra: ghi
vào file QBBUILD.OUT gồm 1 dòng duy nhất là tổng chi phí nhỏ nhất để xây dựng hệ
thống đường
Ví dụ:
QBBUILD.INP
|
QBBUILD.OUT
|
5
2
3 4 1
1
2 10
1
5 1
5
2 1
1
4 1
4
3 3
3
2 2
|
5
|
TEST - CODE - SOLUTION
