Problemas
경주로 여행간 경수는 새로운 것을 많이 구경하고 싶어한다.
해가 질 무렵에, 경수는 오늘 여행의 최종 코스로 불국사에 가고자 하며, 불국사를 갔다가 예약된 숙소로 이동하고자 한다.
모든 길은 양방향으로 통행이 가능하며 어느 두 지점에 대한 길이 여러 개 존재할 수 있다.
새로운 것을 많이 구경하고 싶은 경수는 같은 길을 두 번 다시 가고 싶지 않다.
경수에게 현재 위치에서 불국사를 지나 숙소로 가는 가장 빠른 길을 알아내는 프로그램을 작성하라.
Entrada
입력의 첫째 줄에는 정점의 개수 N과 길의 개수 E가 주어진다. 다음 E개 줄에는 각각 하나씩 길에 대한 정보가 주어진다. 길에 대한 정보는 그 길이 연결하는 두 정점의 번호 v1, v2와 거리를 의미하는 정수 d로 이뤄진다. 1번 정점이 현재 위치, 2번 정점이 불국사, N번 정점이 숙소의 위치다.
<제약조건> 3 ≤ N ≤ 100 2 ≤ E ≤ 2,000 1 ≤ v1, v2 ≤ N 1 ≤ d ≤ 100
Salida
현재 위치에서 불국사에 들린 후 숙소로 가는 가장 빠른 길의 거리를 출력한다. 같은 길을 두 번 이상 지나는 경우는 없으며 같은 정점을 여러번 방문 하는 것은 가능하다.
Ejemplo
4 4
1 3 2
2 3 1
3 4 3
2 4 5
8
Debes iniciar sesión para escribir código.