Informatica Online Judge

  미국여행 [2111 / 083F]

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


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

[koistudy.net (34rd 김태영)]

Background

한 번도 외국에 가본 적이 없는 촌놈 승한이는 17년만에 첫 미국 관광을 갔다.

승한이의 첫 날 미국 관광 일정은 자유의 여신상을 들렀다가 숙소에 가는 것이다.

승한이는 미국의 많은 도로를 구경하고 싶어하기 때문에 갔던 길을 또 가지는 않을 것이다.

승한이를 도와 조건을 만족하여 현재 위치에서 자유의 여신상을 들러 숙소로 가는 최단 거리를 찾아주자.

Input

입력의 첫 번째 줄에는 관광지 개수 $V(3≤V≤100)$와 길의 개수 $E(2≤E≤2000)$가 주어진다.

$E$ 개의 줄에는 길의 시작점 $s_i$, 끝점 $e_i$, 그 길의 거리 $v_i$ 가 주어진다.
($1≤s_i, e_i≤V, 1≤v_i≤100$)

1번 관광지가 현재 위치, 2번 관광지가 자유의 여신상, $N$번 관광지가 숙소의 위치이다.

길은 양방향 도로이다.

두 관광지에 대한 길이 여러 개 존재할 수 있다.

Output

현재 위치에서 자유의 여신상을 들른 뒤 숙소로 가는 최단 거리를 출력하라.
같은 길은 두 번 이상 못 지나가며, 같은 관광지를 두 번 이상 지나가는 것은 허용된다.

IO Example

입력 예시
4 4
1 3 2
2 3 1
3 4 3
2 4 5

출력 예시
8

풀이
1->3->2 (6) , 2->4 (2) 로 6+2=8이 최소이다.

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