문제
그래프가 입력으로 들어왔을 때 1번 정점부터 N번 정점으로 이동할 경우의 최단 경로를 구하는 프로그램을 작성하라.
정점의 개수와 간선의 개수가 크기 때문에 보통의 알고리즘을 이용해서는 제시간에 답을 찾기 어렵기 때문에,
효율적인 알고리즘을 고안하여 프로그램을 작성해 보자.
입력
첫 번째 줄에는 그래프의 정점의 개수 N(N≤100,000)과 간선의 개수 M(M≤1,000,000)이 입력된다.
그 다음 줄부터 M개의 간선의 정보가 입력된다. 간선의 정보는 3개의 정수 a, b, c로 숫자마다
공백을 사이에 두고 입력되는데 정점 a에서 정점 b로 갈 때 c만큼의 비용이 든다는 것을 의미한다.
a와 b는 1이상 N이하의 숫자이며, c의 경우 2만 이하의 양의 정수이며 단방향 간선이다.
출력
1번 경로에서 N번 경로 까지 가는 최단 경로 값을 출력한다.
입력데이터는 결과값이 항상 존재하도록 주어진다.
예제1
입력
44
123
234
342
145
출력
5
출처
comkiwer