문제 1378 학교 가는 길
[만든사람 : ]
문제 설명
세종이가 세종시로 이사하게 되었다. 세종이의 동네에는 n개의 교차로가 있고, 각 교차로마다 번호가 매겨져 있다. 세종이의 집은 1번이고 학교는 n번이다.
세종이의 집과 교차로, 학교를 잇는 도로의 길이가 주어졌을 때 세종이의 집에서 학교까지 가는 가장 빠른 길의 거리는 얼마나 될까?
(자기 교차로로 돌아오는 도로도 있으며, 교차로 간에 도로가 여러 개 있을 수도 있다)
입력 설명
첫번째 줄에 세종이의 집과 학교를 포함한 교차로의 수 n(1 <= n <= 500)과 도로의 수 m(1 <= m <= 4,000)
두번째 줄부터 m줄에 걸쳐 도로의 정보(두 교차로와 교차로 사이의 거리(1 <= 거리 <= 1,000))
두번째 줄부터 m줄에 걸쳐 도로의 정보(두 교차로와 교차로 사이의 거리(1 <= 거리 <= 1,000))
출력 설명
세종이의 집(1)에서 학교(n)까지의 최단 거리
학교까지 가는 길이 없다면 -1을 출력한다.
학교까지 가는 길이 없다면 -1을 출력한다.
입력 예시 복사
6 11
1 2 6
2 3 7
3 6 8
6 5 6
5 4 4
4 1 9
1 1 5
5 1 3
5 3 5
2 5 1
5 6 3
출력 예시 복사
6