Informatica Online Judge

  R&E가는길 도로공사편 (Tiny) [2147 / 0863]

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


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

[JKJeong]

Background

현호가 GSHS에서 R&E 교수님을 뵈러 S대학교를 가려고 한다.

경유하는 지역(GSHS와 S대학교 포함)이 n개, 한 지역에서 다른 지역으로 가는 방법이 총 m개이며 GSHS는 지역 1이고 S대학교는 지역 n이다.

여기서 경곽이는 거리들 중 하나를 확장공사를 하여 가는데 드는 비용을 반으로 줄일 수 있다. 짝수일 경우 정확하게 비용이 반으로 줄어들며, 홀수일 경우 나눈 몫이 된다. (소수점 이하 버림)

이와 같이 도로 하나의 비용을 반으로 줄 일 수 있을 때 현호가 1번 지역에서 n지역까지가는 최소 비용을 구하시오.

단, n은 10 이하, m은 30 이하, 그리고 한 지역에서 다른 지역으로 가는 데에 필요한 비용은 모두 200이하 양의 정수이며 한 지역에서 다른 지역으로 가는 어떠한 방법이 존재하면 같은 방법과 비용을 통해 역방향으로 갈 수 있다.

다음 그래프는 예를 보여준다.(단, 정점a->정점b로의 간선이 여러 개 있을 수 있으며, 자기 자신으로 가는 정점을 가질 수도 있다.)



최소 비용이 드는 경로 : 1→3→5→7
공사를 할 도로 : 1→3, 비용 69/2 = 34
최소 비용 : 34+59+21=114

Input

첫째 줄에는 한 칸씩의 공백을 두어 지역의 수와 한 지역에서 다른 지역으로 가는 총 방법의 수가 주어지며 두 번째 줄부터 m+1줄까지는 한 칸씩의 공백을 두어 각 지역과 그 지역에서 갈 수 있는 지역 그리고 그 지역으로 가는데 필요한 비용이 주어진다.

Output

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

IO Example

입력
7 11
1 2 47
1 3 69
2 4 57
2 5 124
3 4 37
3 5 59
3 6 86
4 6 27
4 7 94
5 7 21
6 7 40

출력
114

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