Nguồn: spoj
Nông dân John quyết định mang
nước tới cho N (1 <= N <= 300) đồng cỏ của mình, để thuận tiện ta đánh số
các đồng cỏ từ 1 đến N. Để tưới nước cho 1 đồng cỏ John có thể chọn 2 cách, 1
là đào ở đồng cỏ đó 1 cái giếng hoặc lắp ống nối dẫn nước từ những đồng cỏ
trước đó đã có nước tới.
Để đào một cái giếng ở đồng cỏ
i cần 1 số tiền là W_i (1 <= W_i <= 100,000). Lắp ống dẫn nước nối 2 đồng
cỏ i và j cần 1 số tiền là P_ij (1 <= P_ij <= 100,000; P_ij = P_ji;
P_ii=0).
Tính xem nông dân John phải chi
ít nhất bao nhiêu tiền để tất cả các đồng cỏ đều có nước.
Dữ liệu
vào: trong file FWATER.INP
+ Dòng 1: Một số nguyên duy
nhất: N
+ Các dòng 2..N + 1: Dòng i+1
chứa 1 số nguyên duy nhất: W_i
+ Các dòng N+2..2N+1: Dòng
N+1+i chứa N số nguyên cách nhau bởi dấu cách; số thứ j là P_ij
Dữ liệu
ra: trong file FWATER.OUT
Một số nguyên duy nhất là chi phí tối thiểu để
cung cấp nước cho tất cả các đồng cỏ.
Ví dụ:
FWATER.INP
|
FWATER.OUT
|
4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0
|
9
|
