[알고리즘] 백준 1753 - 최단경로

문제

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

1753번: 최단경로

 

풀이

그냥 정말 다익스트라 기초 문제.

2달 전에 풀었던 문제인데 메모리 초과, 시간초과, 맞았습니다... 라고 돼있어서 좀 걱정했는데 아니나다를까 이번 처음 풀이도 시간 초과가 떴다. ㅠㅠ 뭐가 문제인지 고민했는데 혹시나..하고 input을 sys로 고쳐줬더니 바로 정답. 아오 이럴 때마다 아주 킹이 받는다.

풀이 적을 것도 없이 일반 다익스트라 문제고, heapq에서 쓸 때 가중치(거리)를 앞에 둬서 최소힙이 유지되게끔 해야한다는 점만 주의하면 될 듯하다.

 

정답 코드

import heapq
import sys


input = sys.stdin.readline
v,e = map(int,input().split())
k = int(input())


graph = [[] for _ in range(v+1)]
# graph = [[1e9 for _ in range(ori_v+1)] for _ in range(ori_v+1)]
visited=[1e9] * (v+1)


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


def dijkstra(x):
    q = []
    heapq.heappush(q,(0,x))
    visited[x] = 0
    
    while q:
        d,x = heapq.heappop(q)
        
        if visited[x] < d:
            continue

        for nw,nx in graph[x]:
            nd = d + nw

            if visited[nx] > nd:
                heapq.heappush(q,(nd,nx))
                visited[nx] = nd


dijkstra(k)
# print(graph[k])
for i in range(1,v+1):
    if visited[i] == 1e9:
        print('INF')
    else:
        print(visited[i])