Informatica Online Judge

  CU 가는길 [2109 / 083D]

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


The Champion of this Problem (C++) : gs16106 - 0ms / 1336byte
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]
Writer ID : [gs16020]

Background

태영이는 아침에 일어나 오늘의 운세 프로그램을 보고 오늘 태영이의 행운의 숫자는 m이라는 것을 깨달았다.

그리고 평화로운 일과를 보낸 태영이는 잠시 CU로 외출을 하려고 한다. 그런데 학교부터 CU까지의 각 골목마다 불량배들이 점령하고 있다는 소식을 들은 태영이는 불량배들을 최대한 피해서 가려고 한다.

그 때, 태영이는 행운의 숫자 m을 기억해내고 왠지 m번째로 만나는 불량배는 자신을 때리지 않을 것 같은 자신감이 생겼다.

만약 정말로 m번째로 만나는 불량배는 태영이를 때리지 않는다면 태영이가 CU로 도착하는 과정에서 불량배로부터 가해질 최소의 피해를 구해보자.

Input

첫 줄에 가능한 경유지의 개수 $n$ (학교, CU 포함) ($1<=n<=300$), 골목의 개수 $k$, 태영이의 행운의 숫자 $m$($1<=m<=8$)이 주어진다.
단, 각 경유지로부터 갈 수 있는 또 다른 경유지의 개수는 10개 이하이다.

두 번째 줄부터 k줄에 걸쳐서 x,y,z가 주어진다. 이는 x경유지에서 y경유지로 이동할 수 있는 골목이 있어 불량배가 태영이를 z만큼의 피해를 줌을 의미한다.($1<=z<=1000$)

골목은 일방통행이며, 1번 경유지는 학교, n번 경유지는 CU이다.

Output

1번 경유지에서 n번 경유지로 골목을 따라 이동할 때 태영이가 받을 수 있는 최소의 피해를 구하라.

단, m번째로 방문하는 골목의 불량배는 태영이에게 피해를 주지 않으며 도착할 수 없는 경우는 주어지지 않는다.

IO Example

입력1
4 5 2
1 2 3
1 3 2
2 3 5
2 4 1
3 4 7

출력1
2

해설 : 1 -> 3 -> 4로 이동하면 두번째로 만나는 불량배는 피해를 주지 않기 때문에 2의 피해만 받고 CU에 도착할 수 있으며 이 경로가 최소이다.

입력2
5 6 3
1 2 5
1 4 2
2 3 10
3 4 7
3 5 9
4 2 1

출력2
12

해설 : 1 -> 4 -> 2 -> 3 -> 5로 가는 것이 2 -> 3의 10의 피해를 무시하고 갈 수 있어서 최소의 피해를 받는다.

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