[ BOJ 1916 ] 최소 비용 구하기(Python)

문제

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

출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력하면 된다.
그나마 다행인(🤔) 점은 출발점에서 도착점을 갈 수 있는 경우만 주어진다는 것~

문제를 제대로 안읽어서 양방향으로 연결하고 한참 해맸다.
우어어 ༼;´༎ຶ ۝ ༎ຶ༽

특정한 최단 거리 를 풀고 이 문제를 풀었는데, 고려할 점이 적어서 쉽게 풀었다.

문제 풀이

1. 출발 도시, 도착 도시를 단방향으로 이어주는 그래프 만들기
2. 그래프 상에서 출발 도시와 연결된 도시들로 이동해준다.
   2-1. 출발 도시에서 다른 도시까지 최단으로 이동할 때 드는 비용을 dist 리스트에 저장한다.
   2-2. dist[이동할 도시]의 값이 (현재 비용 + 이동 비용) 보다 크면, 값을 (현재 비용 + 이동 비용)로 할당해준다.
   ( = 더 작은 값을 최단 비용으로 처리해준다. )
3. dist[도착 도시]의 값을 출력해준다.
   • dist[도착 도시] = 출발 도시에서 도착 도시까지 걸리는 최단 비용이 저장 되어있다.

코드

import sys
import heapq
INF = sys.maxsize
input = sys.stdin.readline

def dijkstra(start_cost,start_node):
    dist = [ INF for _ in range(n+1)]
    dist[start_node] = 0
    q = [(start_cost,start_node)]

    while q:
        print(dist)
        p = heapq.heappop(q)
        cur_cost, cur_node = p[0], p[1]
        for next_cost, next_node in graph[cur_node]:
            if dist[next_node] > cur_cost + next_cost:
                dist[next_node] = cur_cost + next_cost
                heapq.heappush(q, (dist[next_node],next_node))
    return dist

# 도시 개수 n, 버스 개수 m
n = int(input().rstrip())
m = int(input().rstrip())

graph = [ [] for _ in range(n+1) ]

for _ in range(m):
    start,end,cost = map(int,input().rstrip().rsplit())
    graph[start].append((cost,end))

want1, want2 = map(int,input().rstrip().rsplit())
answer = dijkstra(0,want1)
print(answer[want2])