[BOJ] Q1753 최단경로

[BOJ] Q1753 연구소

Question

Language: Python

Difficulty: Gold 5

시작점에서 다른 노드들로 도달하는 최속 거리를 구하는 SSSP 문제로 dijkstra 알고리즘을 이용하면 쉽게 풀이가 가능하다. 여기서 중요한 점은, 노드에서 노드로 가는 길이 여러 갈래가 될 수 있다는 점이다. 따라서, 여러 갈래 중 최소값을 가지는 갈래를 선택해야한다.

Solution

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

    heap=[]        
    heapq.heappush(heap,(0,start))
    
    while heap:
        weight,vertex=heapq.heappop(heap)
        #이미 처리한 노드에 대해서는 재탐색할 필요가 없다. 
        if weight > distance[vertex]:
            continue
        for adj_vertex,cost in graph[vertex]:
            #시작점 노드인 경우 생략
            if adj_vertex == vertex :
                continue
            temp=distance[vertex]+cost
            if distance[adj_vertex] > temp:
                distance[adj_vertex]=temp
                heapq.heappush(heap,(temp,adj_vertex))

    return distance



if __name__ == "__main__":
    vertices,edges=map(int,input().split())
    start=int(input())
    graph=[[] for _ in range(vertices+1)]
    for _ in range(edges):
        v1,v2,w=map(int,input().split())
        graph[v1].append((v2,w))
  
    distance=solution()

    for adj_vertex in range(1,vertices+1):
        if distance[adj_vertex] == inf:
            print("INF")
        else:
            print(distance[adj_vertex])