백준 python 기록

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

우히힝 2021. 10. 26. 23:39

백준 링크:https://www.acmicpc.net/problem/1916

 

1916번: 최소비용 구하기

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

www.acmicpc.net

 

다익스트라 1차원문제

 

다익스트라 알고리즘은

https://brownbears.tistory.com/554

 

[Python] 최단 경로 알고리즘 - 다익스트라 알고리즘 (Dijkstra Algorithm)

최단 경로 알고리즘이란 주어진 노드와 간선(edge)들 중, 가장 짧은 경로를 찾는 알고리즘입니다. 즉, 서울에서 인천, 대전, 광주, 부산을 갈 수 있는 가장 짧은 경로를 찾는 것입니다. 최단 경로

brownbears.tistory.com

이곳에서 배웠다.

import sys
import heapq

n = int(input())
m = int(input())

input = sys.stdin.readline
INF = sys.maxsize
heap = []

dp=[INF]*(n+1)
city=[[] for i in range(n+1)]

for i in range(m):
    u,m,v = map(int,input().split())
    city[u].append((v,m))

def dijkstra(start):

    dp[start] = 0
    heapq.heappush(heap,(0,start))

    while heap:
        w_now,now = heapq.heappop(heap)

        if dp[now] < w_now:
            continue

        for wei,node in city[now]:

            next_w = w_now + wei

            if dp[node] > next_w:
                dp[node] = next_w
                heapq.heappush(heap,(next_w,node))

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

dijkstra(start)

print(dp[end])