최단경로 > 문제은행

본문 바로가기


알고리즘 자료구조2

1941 : 최단경로

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 278 회    시도횟수: 2042 회   



그래프가 입력으로 들어왔을 때 1번 정점부터 N번 정점으로 이동할 경우의 최단 경로를 구하는 프로그램을 작성하라.


정점의 개수와 간선의 개수가 크기 때문에 보통의 알고리즘을 이용해서는 제시간에 답을 찾기 어렵기 때문에, 효율적인 알고리즘을 고안하여 프로그램을 작성해 보자.


첫 번째 줄에는 그래프의 정점의 개수 N(N≤20,000)과 간선의 개수 M(M≤100,000)이 입력된다. 그 다음 줄부터 M개의 간선의 정보가 입력된다. 간선의 정보는 3개의 정수 a, b, c로 숫자마다 공백을 사이에 두고 입력되는데 정점 a에서 정점 b로 갈 때 c만큼의 비용이 든다는 것을 의미한다. a와 b는 1이상 N이하의 숫자이며, c의 경우 1만 이하의 양의 정수이며, 간선을 통해 a에서 b로만 이동이 가능하나, b에서 a로는 이동이 불가능한 단방향 간선이다.



1번 경로에서 N번 경로 까지 가는 최단 경로 값을 출력한다.


[Copy]
4 4
1 2 3
2 3 4
3 4 2
1 4 5
[Copy]
5



HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.