파일 업로드

워터링 홀

profile
실행 시간 제한메모리 제한
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)의 비용이 든다.

농부 존이 모든 풀밭에 물을 공급하기 위해 지불해야 할 최소비용을 정하시오.

💻 입력
  • 1번째 줄: 하나의 정수: N
  • 2번째 줄 ~ N+1번째 줄: i+1 번째 줄은 하나의 정수를 포함합니다: W_i
  • N+2번째 줄 ~ 2N + 1번째 줄: N+1 + i 번째 줄은 N개의 공백으로 구분된 정수를 포함하며, j번째 정수는 P_ij입니다.
🖨️ 출력
  • 1번째 줄: 모든 풀밭에 물을 공급하는데 필요한 최소비용인 하나의 정수를 포함하는 단일 줄

💻 예제 입력 1
4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0
🖨️ 예제 출력 1
9

출처: USACO 2008 October Gold 3