[백준 파이썬] 1916 최소비용 구하기

1916번: 최소비용 구하기

문제

 

도시와 버스의 노선, 그리고 노선에 대한 비용이 주어진다. 도시 두개가 주어진 후 해당 도시를 가장 적은 비용으로 갈 때 해당 비용을 구하는 문제이다.

---

알고리즘

그래프경로의 최소값을 구해야 하고 가중치가 주어졌으므로 "다익스트라"알고리즘을 사용해야겠다고 생각했다. 

 

다익스트라 알고리즘은 이전에 1504번 특정한 최단 경로 문제에서 소개하였으므로 넘어간다.

https://dudgus907.tistory.com/manage/newpost/19?returnURL=https%3A%2F%2Fdudgus907.tistory.com%2Fmanage%2Fposts&type=post

풀이

버스의 노선에 대해 왕복은 하지 않으므로 edges에는 하나의 간선정보만 넣어두었다.

edges = [[] for _ in range(N + 1)]

for i in range(M):
    a, b, c = map(int, input().split())
    edges[a].append((b, c))

 

 

이후 다익스트라를 구현하기 위해 다음과 같이 코드를 작성하였다.

def dijkstra(start, end):
    route = [sys.maxsize] * (N + 1)
    route[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while q:
        dist, node = heapq.heappop(q)

        if route[node] < dist:
            continue

        for adjaNode, adjaW in edges[node]:
            cal = route[node] + adjaW

            if cal < route[adjaNode]:
                route[adjaNode] = cal
                heapq.heappush(q, (cal, adjaNode))
    return route[end]

 

이 후 거리(route)값을 구하기 위하여 함수를 호출 후 출력하였다.

route = dijkstra(start, end)
print(route)

 

---

코드

import sys
import heapq
input = sys.stdin.readline
N = int(input())
M = int(input())

edges = [[] for _ in range(N + 1)]

for i in range(M):
    a, b, c = map(int, input().split())
    edges[a].append((b, c))

start, end = map(int, input().split())


def dijkstra(start, end):
    route = [sys.maxsize] * (N + 1)
    route[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while q:
        dist, node = heapq.heappop(q)

        if route[node] < dist:
            continue

        for adjaNode, adjaW in edges[node]:
            cal = route[node] + adjaW

            if cal < route[adjaNode]:
                route[adjaNode] = cal
                heapq.heappush(q, (cal, adjaNode))
    return route[end]


route = dijkstra(start, end)
print(route)