[백준] 1753번: 최단 경로 문제 풀이 파이썬
문제 링크
https://www.acmicpc.net/problem/1753
풀이 방식
- 기존 다익스트라 문제에서 K번 정점부터 각 노드간의 거리를 출력하는 문제이다.
- 이 때, 해당 노드와 연결되어있지 않으면 distance 리스트에는 INF(1e9)로 저장되어있기 때문에, 거리가 INF와 같으면 문자열 'INF'로 대체하여 출력한다.
전체 코드
from sys import stdin
import heapq
INF = int(1e9)
def dijkstra(i):
queue = []
heapq.heappush(queue, (0, i))
distance = [INF] * (V+1)
distance[i] = 0
while queue:
dist, index = heapq.heappop(queue)
if distance[index] < dist:
continue
for node_index, node_dist in graph[index]:
cost = dist + node_dist
if distance[node_index] > cost:
distance[node_index] = cost
heapq.heappush(queue, (cost, node_index))
return distance
V, E = map(int, stdin.readline().split())
graph = {}
for i in range(1, V+1):
graph[i] = []
K = int(input())
for _ in range(E):
u, v, w = map(int, stdin.readline().split())
graph[u].append([v, w])
ans = dijkstra(K)
for i in ans[1:]:
if i == INF:
print("INF")
else:
print(i)
Author And Source
이 문제에 관하여([백준] 1753번: 최단 경로 문제 풀이 파이썬), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hyuntall/백준-1753번-최단-경로-문제-풀이-파이썬저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)