페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8339
다국어

길 정비하기(revamping trails) 2s 256MB

문제

농부 태웅이는 아버지 일을 물려받아 성실하게 소를 키우고 있다.

목초지 사이에는 M(1 ≤ M ≤ 50,000)개의 길이 존재하며,

그 길을 따라 1번 목초지에서 N번 목초지로 이동해야 한다. (이동이 불가능한 경우는 주어지지 않는다)

태웅이의 농장에는 N(1 ≤ N ≤ 10,000)개의 목초지가 있으며, 각각 1번부터 N번까지 번호가 매겨져 있다.

현재 이 목초지들은 양방향 비포장 길로 연결되어 있다.

각 길 i는 목초지 P1_i와 P2_i(1 ≤ P1_i ,\ P2_i ≤ N)를 연결하며, 이동하는 데 T_i(1 ≤ T_i ≤ 1,000,000)만큼의 시간이 걸린다.

게으른 태웅이는 긴 이동 시간을 줄이기 위해 일부 길을 정비하려고 한다.

최대 K(1 ≤ K ≤ 20)개의 길을 선택하여 고속도로로 바꾸면, 해당 길의 이동 시간이 0이 된다.

태웅이가 최소 시간으로 이동할 수 있도록 길을 정비해주자.


입력

  • 첫 번째 줄: 세 개의 정수 N, M, K가 공백으로 구분되어 주어진다.

  • 두 번째 줄부터 M+1번째 줄까지: 각 줄은 길 i를 나타내며, 세 개의 정수 P1_i, P2_i, T_i가 공백으로 구분되어 주어진다.
    (목초지 P1_i와 P2_i 를 연결하는 길의 이동 시간은 T_j 이다.)


출력

  • 첫 번째 줄: 최대 K개의 길을 정비한 후의 최단 경로 길이를 출력한다.


예제 

4 4 1
1 2 10
2 4 10
1 3 1
3 4 100
1

K=1 이므로 [3→4]를 정비하여 이동 시간을 100에서 0으로 줄인다.

새로운 최단 경로는 [1→3→4]이며, 총 이동 시간은 1이 된다.



출처

USACO 2009 February Gold

로그인해야 코드를 작성할 수 있어요.