R00733
최단 경로
골드 IV레이팅
의견: 0
설명
방향 그래프가 주어진다. 주어진 시작 정점에서 다른 모든 정점으로 가는 최단 경로의 길이를 구하여라. 모든 간선의 가중치는 양의 정수이다.
두 정점 사이에 여러 간선이 있을 수 있으며, 자기 자신으로 가는 간선이 있을 수도 있다.
제약
\(1 \le V \le 20\,000\), \(1 \le E \le 300\,000\), \(1 \le K \le V\), \(1 \le w \le 10\).
입력 형식
첫째 줄에 정점의 개수 \(V\)와 간선의 개수 \(E\)가 주어진다.
둘째 줄에 시작 정점의 번호 \(K\)가 주어진다.
셋째 줄부터 \(E\)개의 줄에 걸쳐 간선의 정보 \(u\ v\ w\)가 주어진다. 이는 정점 \(u\)에서 정점 \(v\)로 가는 가중치 \(w\)인 간선이 있다는 뜻이다.
출력 형식
\(V\)개의 줄에 걸쳐, \(i\)번째 줄에 \(K\)번 정점에서 \(i\)번 정점으로 가는 최단 거리를 출력한다. 경로가 존재하지 않으면 INF를 출력한다.
예제 1
입력
5 7
1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6
4 5 1
3 5 9
출력
0
2
3
7
8
설명
1→2(2), 1→3(3), 1→2→4(7), 1→2→4→5(8).
예제 2
입력
3 1
1
1 2 5
출력
0
5
INF
설명
정점 3은 도달 불가 → INF.
문제 시리즈
문제 정보
riseoj 작성
출처 Original
태그
평가 및 의견
최단 경로
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
최단 경로
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기