[백준]최단경로
문제
https://www.acmicpc.net/problem/1753
풀이
- 간선마다 가중치가 존재하며, 시작 지점에서 각 지점까지의 최단 경로를 구하는 문제다
- 간선마다 가중치가 존재하기에 다익스트라 알고리즘으로 먼저 접근했다.
- 다익스트라 알고리즘에서 BFS를 사용할 때, 기본 큐 대신 우선순위큐를 사용해 시간 복잡도를 O(NlogN)으로 풀어냈다.
코드
from collections import defaultdict
import sys, heapq
input = sys.stdin.readline
# 입력값으로 그래프 그리기
v_num, e_num = map(int, input().split(" "))
start = int(input())
graph = defaultdict(list)
for _ in range(e_num):
a, b, c= map(int, input().split(" "))
graph[a].append((c,b))
# 우선순위큐를 사용해 bfs
queue = [(0,start)]
dist = defaultdict(int)
while queue:
weight, node = heapq.heappop(queue)
if node not in dist:
dist[node] = weight
for cw, cv in graph[node]:
alt = weight + cw
heapq.heappush(queue, (alt, cv))
# 시작점에서 자기자신을 포함해 모든 정점까지의 최단거리 구하기
for i in range(1, v_num+1):
if i in dist:
print(dist[i])
else:
print("INF")
Author And Source
이 문제에 관하여([백준]최단경로), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ddaynew365/백준최단경로저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)