Tưới nước đồng cỏ
View as PDFNông dân John quyết định mang nước tới cho ~N~ (~1 \leq N \leq 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 \leq~ ~W_i~ ~\leq 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 \leq~ ~P_{ij}~ ~\leq 100000~; ~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.
Input
- 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}~
Output
- Dòng ~1~: 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ỏ.
Sample Input
4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0
Sample Output
9
Note
Có 4 đồng cỏ. Mất 5 tiền để đào 1 cái giếng ở đồng cỏ 1, 4 tiền để đào ở đồng cỏ 2, 3 và 3 tiền để đào ở đồng cỏ 4. Các ống dẫn nước tốn 2, 3, và 4 tiền tùy thuộc vào nó nối đồng cỏ nào với nhau.
Nông dân John có thể đào 1 cái giếng ở đồng cỏ thứ 4 và lắp ống dẫn nối đồng cỏ 1 với tất cả 3 đồng cỏ còn lại, chi phí tổng cộng là 3 + 2 + 2 + 2 = 9.
Comments
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.