[백준] 1916번 최소비용 구하기 (Python)

1916번: 최소비용 구하기 (acmicpc.net)

1916번: 최소비용 구하기

다익스트라 문제

 

특정 출발점으로부터 특정 도착점까지의 최소비용을 묻고 있기 때문에, 하나의 출발점에 대한 비용행렬을 만들면 된다!! (1차원 행렬)

 

 

📢 주의해야 하는 점

• 방향 그래프이다!! (처음에 무방향 그래프라고 생각했다가 틀렸다...😥)
• 한 노드로부터 다른 노드로 가는 간선이 여러 개일 수 있다!!

 

예를 들어, 입력이 다음과 같이 주어지면,

1 2 3
1 2 10

 

비용이 적은 첫번째 간선을 선택하도록 해야한다.

 

 

다익스트라와 플로이드-와샬의 차이점은 아래 포스트를 참고

2021/02/25 - [Algorithm/Graph] - [프로그래머스] 합승 택시 요금 (Python)

[프로그래머스] 합승 택시 요금 (Python)

import sys
from math import inf
from heapq import heappush, heappop
read = lambda: sys.stdin.readline().strip()


def dijkstra(graph, start):
    dist = [inf for _ in range(n)]
    dist[start] = 0
    q = []
    heappush(q, [0, start])
    while q:
        cur_dist, cur_node = heappop(q)
        if dist[cur_node] >= cur_dist:
            for i in range(n):
                new_dist = cur_dist + graph[cur_node][i]
                if new_dist < dist[i]:
                    dist[i] = new_dist
                    heappush(q, [new_dist, i])
    return dist


n = int(read())
m = int(read())
costs = [[inf] * n for _ in range(n)]
for _ in range(m):
    u, v, c = map(int, read().split())
    if costs[u - 1][v - 1] != inf and costs[u - 1][v - 1] <= c:
        continue
    costs[u - 1][v - 1] = c
dep, arr = map(int, read().split())
dep, arr = dep - 1, arr - 1

result = dijkstra(costs, dep)
print(result[arr])