6070 : 네트워크 지연 (Dijkstra)
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
네트워크 지연 — 다익스트라 알고리즘
N개의 노드, E개의 방향 간선이 있는 가중치 그래프에서
시작 정점 K에서 모든 정점까지의 최단 거리를 구하시오.
알고리즘: 우선순위 큐(
시간복잡도: $O((N + E) \log N)$
도달할 수 없는 정점은 "INF"를 출력합니다.
[제약 조건]
• 정점 수 $N$: $1 \le N \le 100{,}000$ (정수)
• 간선 수 $E$: $1 \le E \le 200{,}000$ (정수)
• 간선 가중치: $1 \le w \le 10^6$ (정수)
N개의 노드, E개의 방향 간선이 있는 가중치 그래프에서
시작 정점 K에서 모든 정점까지의 최단 거리를 구하시오.
알고리즘: 우선순위 큐(
heapq)를 활용한 다익스트라(Dijkstra)시간복잡도: $O((N + E) \log N)$
도달할 수 없는 정점은 "INF"를 출력합니다.
[제약 조건]
• 정점 수 $N$: $1 \le N \le 100{,}000$ (정수)
• 간선 수 $E$: $1 \le E \le 200{,}000$ (정수)
• 간선 가중치: $1 \le w \le 10^6$ (정수)
입력 설명
첫째 줄에 정점 수 N (1 ≤ N ≤ 10,000)과 간선 수 E (1 ≤ E ≤ 100,000)가 주어집니다.
둘째 줄에 시작 정점 K가 주어집니다.
셋째 줄부터 E개의 줄에 간선 정보 u v w (양의 가중치)가 주어집니다.
둘째 줄에 시작 정점 K가 주어집니다.
셋째 줄부터 E개의 줄에 간선 정보 u v w (양의 가중치)가 주어집니다.
출력 설명
시작 정점 K에서 모든 정점(1~N)으로의 최단 거리를 공백으로 구분하여 출력합니다.
도달 불가능한 경우 INF를 출력합니다.
도달 불가능한 경우 INF를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 5
1
1 2 1
1 3 4
2 3 2
2 4 5
3 4 1
출력 예시
COPY
복사되었습니다!
복사되었습니다!
0 1 3 4