KOISTUDY

Informatica Online Judge

R&E가는길 공사편 2 [2810 / 0AFA]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 438 Total Tried : 2240

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

[koistudy.net (unkonwn)]

Background

경곽이가 GSHS에서 R&E 교수님을 뵈러 S대학교를 가려고 한다.
경유하는 지역(GSHS와 S대학교 포함)이 n개, 한 지역에서 다른 지역으로 가는 방법이 총 m개이며 GSHS는 지역 1이고 S대학교는 지역 n이다.

여기서 경곽이는 거리들 중 하나를 확장공사를 하여 가는데 드는 비용을 반으로 줄인다. (2024.5.16.수정)
짝수일 경우 정확하게 비용이 반으로 줄어들며, 홀수일 경우 나눈 몫이 된다. (소수점 이하 버림)
이와 같이 이동 하는 경로상 도로 하나의 비용을 반으로 줄 일때 현호가 1번 지역에서 n지역까지가는 비용이 k번째로 작은 비용을 구하시오.

단, n은 10 이하, m은 n*(n-1)/2 이하, k는 10000 이하 그리고 한 지역에서 다른 지역으로 가는 데에 필요한 비용은 모두 10000이하 양의 정수이며 한 지역에서 다른 지역으로 가는 어떠한 방법이 존재하면 같은 방법과 비용을 통해 역방향으로 갈 수 있다. 단, 한번 방문한 지역은 방문하지 않는다.

다음 그래프는 예를 보여준다.

공사를 진행하였을 때 첫 번째로 작은 비용은 1->3->5->7 경로에서 1->3 도로를 공사하는 경우로 114의 비용이 필요하며, 두 번째로 작은 비용은 3->5 도로를 공사하는 경우로 119의 비용이 필요하다.

Input

첫째 줄에는 한 칸씩의 공백을 두어 지역의 수와 한 지역에서 다른 지역으로 가는 총 방법의 수 그리고 k가 주어지며 두 번째 줄부터 m+1줄까지는 한 칸씩의 공백을 두어 각 지역과 그 지역에서 갈 수 있는 지역 그리고 그 지역으로 가는데 필요한 비용이 주어진다. (두 정점 사이에 2개 이상의 간선이 존재할 수 있다.)

Output

첫째 줄에 도로 공사를 완료한 후 S대학교를 가는데 드는 k번째의 최소 비용을 출력한다. 만약 현호가 S대학교를 갈 수 없거나 k번째의 최소 비용이 없으면 "-1"을 첫째 줄에 출력한다.(단, 큰따옴표는 출력하지 않는다)

( 단, 비용이 100 101 101 101 102 102 103 순일때. 3번째 비용은 101로 본다.)

IO Example