1753 최단경로

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

1753번: 최단경로

 

해결법

이 문제는 다익스트라 알고리즘을 활용해서 푸는 문제다. graph에 연결된 노드를 저장할 때는 플로이드 알고리즘과 다르게 저장한다는 점을 다시 기억하면 좋을 것 같다. 다익스트라 알고리즘에서 graph에 연결된 노드를 저장하는 법은 시작 노드 a, 연결된 노드 b, 가중치 c를 graph[a].append(b, c)이다. 이 점을 유의하고 푼다면 좀 더 빨리 문제를 풀 수 있을 것 같다.

플로이드 알고리즘으로도 문제를 풀어봤지만 메모리 초과가 발생했다.

 

코드

import heapq

v, e = map(int, input().split())
start = int(input())
INF = int(1e9)

graph = [[] for i in range(v+1)]
distance = [INF] * (v+1)

for i in range(e):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))

def dijkstra(start):
    distance[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    
    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(distance[i])
    else:
        print("INF")

이 처럼 다익스트라 알고리즘을 활용해서 문제를 풀 수 있다.