문제 번호 1461. -- 최단경로, 5점1461: 최단경로, 5점
시간 제한: 1 Sec 메모리 제한: 128 MB
제출: 31 해결 문제 수: 13
[제출][채점 상황 열람][게시판]문제 설명
directed graph가 주어지면 주어진 시작 vertex에서 다른 모든 vertex로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 edge의 weight는 10 이하의 자연수이다.
입력
첫째 줄에 vertex의 개수 V와 edge의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 vertex에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 vertex의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 edge을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 weight w인 edge가 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 vertex 사이에 여러 개의 edge가 존재할 수도 있음에 유의한다.
출력
첫째 줄에 vertex 1부터 V개의 줄에 걸쳐, i번째 줄에 i번 vertex으로의 최단 경로의 경로값을 출력한다. 시작 vertex 자신의 경로값은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.
입력 예시
5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6
출력 예시
0
2
3
7
INF
도움말
출처
[제출][채점 상황 열람]