실행 시간 제한 | 메모리 제한 |
---|---|
2 초 | 128 MB |
농부 존은 N (1 <= N <= 300) 개의 풀밭에 물을 공급하기로 결정했고, 이 때 풀밭들은 편리하게 1..N 까지로 번호가 매겨져 있다. 그는 풀밭에 우물을 파는 것이나, 이미 물이 공급된 다른 풀밭과 파이프로 연결하여 물을 공급할 수 있다.
풀밭 i에 우물을 파는 데는 W_i (1 <= W_i <= 100,000)의 비용이 든다. 풀밭 i와 j를 파이프로 연결하는 데는 P_ij (1 <= P_ij <= 100,000; P_ij = P_ji; P_ii=0)의 비용이 든다.
농부 존이 모든 풀밭에 물을 공급하기 위해 지불해야 할 최소비용을 정하시오.
4 5 4 4 3 0 2 2 2 2 0 3 3 2 3 0 4 2 3 4 0
9