레이팅 미적용농부 존(Farmer John)이 이사를 간다! 존은 매일 이동해야 하는 거리를 최소화할 수 있는, 새 농장을 짓기에 가장 좋은 장소를 찾으려 한다.
FJ가 이사하려는 지역에는 N개 (1 <= N <= 10,000)의 마을이 있다. 특정 마을 쌍들을 연결하는 M개 (1 <= M <= 50,000)의 양방향 도로가 있다. 도로들을 적절히 조합하면 모든 마을에서 다른 모든 마을로 갈 수 있다. FJ가 새 농장의 터로 가장 좋은 마을을 고르는 데 당신의 도움이 필요하다.
K개 (1 <= K <= 5)의 마을에는 FJ가 매일 방문하고 싶은 시장이 있다. 구체적으로, 존은 매일 새 농장을 떠나 시장이 있는 K개의 마을을 방문한 뒤 농장으로 돌아올 계획이다. FJ는 시장들을 원하는 순서로 방문할 수 있다. 새 농장을 지을 마을을 고를 때, FJ는 시장이 없는 N-K개의 마을 중에서만 고르고 싶어 한다. 그런 마을들의 집값이 더 싸기 때문이다.
FJ가 최적의 위치에 농장을 짓고 시장 방문 일정을 최대한 영리하게 짤 때, 매일의 일정 동안 이동해야 하는 최소 거리를 계산하는 것을 도와주자.
첫째 줄: 공백으로 구분된 세 정수 N, M, K.
둘째 줄부터 1+K번째 줄까지: i+1번째 줄에 i번째 시장이 있는 마을을 나타내는 1...N 범위의 정수가 주어진다. 각 시장은 서로 다른 마을에 있다.
2+K번째 줄부터 1+K+M번째 줄까지: 각 줄에 공백으로 구분된 세 정수 i, j (1 <= i,j <= N), L (1 <= L <= 1000)이 주어지며, 마을 i에서 마을 j로 가는 길이 L의 도로가 있음을 나타낸다.
FJ가 최적의 위치에 농장을 지을 때, 매일의 일과 동안 이동해야 하는 최소 거리.
relocate.in · 출력을 쓸 파일 relocate.out5 6 3
1
2
3
1 2 1
1 5 2
3 2 3
3 4 5
4 2 7
4 5 1012Input details: There are 5 towns, with towns 1, 2, and 3 having markets. There are 6 roads.
Output details: FJ builds his farm in town 5. His daily schedule takes him through towns 5-1-2-3-2-1-5, for a total distance of 12.
riseoj 작성
출처 올림피아드 > USACO > 2011-2012 > February > Silver