8041 : 가장 단거리 경로 I
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$개의 도시와 이들을 잇는 $M$개의 단방향 비행기 노선이 주어집니다. 각 노선에는 비행 거리가 소요 가중치로 붙어 있습니다.
1번 도시에서 출발하여 각 도시($1$번부터 $N$번 도시까지)에 도달할 수 있는 가장 짧은 비행 거리를 구하는 프로그램을 작성하시오.
[제약 조건]
• $1 \le N \le 100{,}000$
• $1 \le M \le 200{,}000$
• $1 \le a, b \le N$
• $1 \le c \le 10^9$
1번 도시에서 출발하여 각 도시($1$번부터 $N$번 도시까지)에 도달할 수 있는 가장 짧은 비행 거리를 구하는 프로그램을 작성하시오.
[제약 조건]
• $1 \le N \le 100{,}000$
• $1 \le M \le 200{,}000$
• $1 \le a, b \le N$
• $1 \le c \le 10^9$
입력 설명
첫째 줄에 도시의 수 $N$과 노선의 수 $M$이 주어집니다. ($1 \le N \le 100,000$, $1 \le M \le 200,000$)
다음 $M$개의 줄에 걸쳐 노선의 출발지 $a$, 목적지 $b$, 비행 거리 $c$가 공백으로 구분되어 주어집니다. ($1 \le a, b \le N$, $1 \le c \le 10^9$)
다음 $M$개의 줄에 걸쳐 노선의 출발지 $a$, 목적지 $b$, 비행 거리 $c$가 공백으로 구분되어 주어집니다. ($1 \le a, b \le N$, $1 \le c \le 10^9$)
출력 설명
1번 도시에서 각 도시(1번부터 )로 가는 최단 거리를 공백으로 구분하여 한 줄에 출력합니다. 만약 1번 도시에서 해당 도시에 갈 수 없는 노선인 경우 -1을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 4
1 2 6
1 3 2
3 2 3
1 3 4
출력 예시
COPY
복사되었습니다!
복사되었습니다!
0 5 2도움
음수 가중치가 없는 단일 시작점 최단 거리 알고리즘인 다익스트라(Dijkstra) 알고리즘을 사용합니다.
우선순위 큐(Heap)를 사용하여 $O(E \log V)$ 시간에 구현합니다. 파이썬에서는
우선순위 큐(Heap)를 사용하여 $O(E \log V)$ 시간에 구현합니다. 파이썬에서는
heapq 라이브러리를 사용하며, 힙에는 항상 (거리, 정점) 순서로 값을 넣어 첫 번째 요소인 '거리'를 기준으로 힙 정렬이 수행되도록 처리하십시오.