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

HRuler 2023. 7. 31. 19:30

1. 문제

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

1916번: 최소비용 구하기

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그

www.acmicpc.net

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])