EDOC 2023-W 4회차 정모 (다익스트라 / 벨만-포드)

A. 지름길 (백준 1446번)

 

https://www.acmicpc.net/problem/1446

 

#python

from sys import stdin
import sys
from queue import PriorityQueue

n, d = map(int, stdin.readline().split())
g = [[] for _ in range(10001)]
visited = [False] * (10001)
dst = [sys.maxsize] * (10001)
que = PriorityQueue()

for i in range(d):
    g[i].append((i+1, 1))

for _ in range(n):
    a, b, c = map(int, stdin.readline().split())
    g[a].append((b, c))

dst[0] = 0
que.put((0, 0))

while que.qsize() > 0:
    now = que.get()
    if visited[now[1]]:
        continue
    visited[now[1]] = True
    for next in g[now[1]]:
        if dst[now[1]] + next[1] < dst[next[0]]:
            dst[next[0]] = dst[now[1]] + next[1]
            que.put((dst[next[0]], next[0]))

print(dst[d])

처음에는 g = [[] for _ in range(d+1)] 이렇게 했고 그래프 배열뿐만 아니라 visited 배열, dst 배열 모두 d+1까지만 만들었다. 그러니까 인덱스 에러가 떴다. 바로 g[i].append((i+1, 1)) 이렇게... d를 넘어서도 배열에 들어갈 수 있기 때문... 그래서 g 배열, visited 배열, dst 배열 다 10001까지 (문제 조건에 따라) 선언해주니까 정상적으로 돌아갔다. (정답)