Informatica Online Judge

  목초지 최소 이동 시간 [1478 / 05C6]

Time Limit(Test case) : 2000 (ms)
Number of users who solved : 23   Total Tried : 253


The Champion of this Problem (C++) : gs15088 - ms / 1136byte
My Best Submission (C++) : N/A

[FEB09]

Background

농부 존은 소들이 목초지에서 목초지로 이동하는 것을 점검해야 한다.

길은 1 에서 M (1 <= M <= 50,000)까지 번호가 부여되어 있고 1 번 목초지에서 N 번 목초지로 길이 있다(주어진 입력에서는 1 번 목초지에서 N 번 목초지로 연결되어 있다)

1 에서 N (1 <= N <= 10,000)까지 번호가 매겨진 목초지는 양방향 길로 연결되어 있다.

i 번 째 길은 목초지 P1_i 와 P2_i (1 <= P1_i <= N; 1 <= P2_i <= N)에 연결되어 있고 Ti (1 <= T_i <= 1,000,000)만큼의 시간이 소요된다.

그는 이 길 중 몇 길을 개선하려고 한다.

특별히 , 그는 K (1 <= K <= 20)개의 길을 선택해서 이 길을 고속도로로 만들어 이동시간을 0 으로 만들려고 한다.

존을 도와 목초지 1 에서 N 까지 가는 최소 시간을 찾아라.

Input

첫 째 줄에 세 정수 N, M, K가 공백으로 구분되어 입력된다.
i+1 번 째 줄은 길 i 의 P1_i, P2_i, and T_i 가 정수로 주어진다.

Output

많아야 K 개의 길을 개량 한 후의 가장 짧은 길의 크기를 출력한다.

IO Example

입력
4 4 1
1 2 10
2 4 10
1 3 1
3 4 100

출력
1

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]