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

문제

 

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

1916번: 최소비용 구하기

 

---

Algorithm

 

다익스트라 문제이다. 문제에서 버스가 왕복하지 않으므로 양방향이 아닌 단방향으로 그래프에 값을 넣어주면 된다.

시작지점을 입력받아 주어진 출발점을 설정하고 다익스트라 알고리즘을 실행해 주면 된다.

문제에서 '출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.'로 제시해주었으므로 시작지점부터 다른 노드들 사이의 최소가중치를 가지고 있는 배열 distance의 t번째 원소를 출력해주면 된다.

---

 

 

Code

import sys
import heapq
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n = int(input())	#정점의 개수
m = int(input())	#간선의 개수

INF = int(1e9)
graph = [[] * (n+1) for _ in range(n+1)]	#그래프초기화
distance = [INF]*(n+1)	#거리 초기화

for _ in range(m):	#간선 입력
    a,b,c = map(int,input().split())
    graph[a].append((b,c))	#버스는 편도로 운행하므로 단방향 간선으로 넣어준다

s,t = map(int,input().split())	#시작점과 도착점 입력

def dijkstra(start,distance,graph):	#다익스트라
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

dijkstra(s,distance,graph)	#시작점을 s로 하여 다익스트라 실행

print(distance[t])	#도착점의 최소비용 출력