[BOJ] Q1916 최소비용 구하기

[BOJ] Q1916 최소비용 구하기

Question

Language: Python

Difficulty: Gold 5

특정 출발지에서 특정 도착지로의 최소 거리를 구하는 SSSP문제로 dijkstra 알고리즘으로 쉽게 해결가능하다.

Tip

if distance[vertex] < weight:
    continue

Solution

from math import inf
import heapq
def dijkstra():
    distance=[inf]*(vertices+1)
    distance[start]=0

    heap=[]        
    heapq.heappush(heap,(0,start))
    
    while heap:
        weight,vertex=heapq.heappop(heap)

        if distance[vertex] < weight:
            continue

        for adj_vertex,cost in graph[vertex]:
            temp=distance[vertex]+cost
            if distance[adj_vertex] > temp:
                distance[adj_vertex]=temp
                heapq.heappush(heap,(temp,adj_vertex))

    return distance[end]



if __name__ == "__main__":
    vertices=int(input())
    edges=int(input())
    graph=[[] for _ in range(vertices+1)]

    for _ in range(edges):
        v1,v2,w=map(int,input().split())
        graph[v1].append((v2,w))
  
    start,end=map(int,input().split())
    distance=dijkstra()
    print(distance)