(Python)백준 코딩테스트 연습 - 최소비용 구하기(1916)

1. 문제

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

1916번: 최소비용 구하기

2. 풀이

# import 코드
import sys
input = sys.stdin.readline
from collections import deque

# 입력 코드
# n : 도시 수
n = int(input())
# m : 버스 수
m = int(input())
# graph : 버스 정보 그래프 배열
graph = [[] for i in range(n+1)]
for i in range(m):
    s, e, c = map(int, input().split())
    graph[s].append([e, c])
# st, en : 출발지와 도착지
st, en = map(int, input().split())

costs = [sys.maxsize for i in range(n+1)]
costs[st] = 0
q = deque()
q.append([costs[st], st])

while q:
    cost, cSt = map(int, q.popleft())
    
    if costs[cSt] < cost:
        continue
    
    for nextPosi, nextCost in graph[cSt]:
        totalCost = cost + nextCost
        if totalCost < costs[nextPosi]:
            costs[nextPosi] = totalCost
            q.append([totalCost, nextPosi])

print(costs[en])