BOJ - 1753

백준 문제 링크
최단경로

❓접근법

1. 다익스트라 알고리즘을 활용했다.
2. e번의 반복문으로 a, b, c를 받아서
   graph[a]에 정점(b)과 가중치(c)를 넣고,
   distance = [INF] * (v + 1)로 지정한다.
3. 기본 다익스트라 함수를 적용하고,
   거리가 INF인 것은 'INF'를 출력하고, 나머지는 그대로 출력하면 끝!

👌🏻코드

import heapq

INF = int(1e9)

v, e = map(int, input().split())

start = int(input())

graph = [[] for _ in range(v + 1)]

distance = [INF] * (v + 1)

for _ in range(e):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    
def dijkstra(start):
    
    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(start)

for i in range(1, v + 1):
    if distance[i] == INF:
        print('INF')
    else:
        print(distance[i])