Informatica Online Judge

  R&E가는길 (Large) [0479 / 01DF]

Time Limit(Test case) : 1500(ms)
Number of users who solved : 197   Total Tried : 278


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

[]

Background

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

경유하는 지역(GSHS와 S대학교 포함)이 n개, 한 지역에서 다른 지역으로 가는 방법이 총 m개이며 GSHS는 지역 1이고 S대학교는 지역 n이라고 할 때 현호가 S대학교로 가는데 드는 최소 비용을 구하시오.

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

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



최소 비용이 드는 경로 : 1→3→5→7
최소 비용 : 69+59+21=149

Input

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

Output

첫째 줄에 S대학교를 가는데 드는 최소 비용을 출력한다. 만약 현호가 S대학교를 갈 수 없다면 "Impossible"를 첫째 줄에 출력한다.(단, 큰따옴표는 출력하지 않는다)

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

출력
149

출제 - 최현호 (GSHS_28th)

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