[python]1753번 최단경로, heapq는 첫번째 값 기준으로 한다.

처음에는 우선순위 큐를 적용하지 않고 풀이를 진행하였다.

import sys
from collections import deque
input = sys.stdin.readline
node,edge = map(int,input().split())
start = int(input().strip())
graph = [[]for i in range(node+1)]
for i in range(edge):
    fst,scd,thd = map(int,input().split())
    graph[fst].append((scd,thd))
visit = [0 for i in range(node+1)]
mrst = [1e9 for i in range(node+1)]
mrst[start] = 0
visit[start] = 1
que = deque()
que.append(start)
while que:
    cur = que.popleft()
    for next in graph[cur]:
        if mrst[next[0]]<mrst[cur]+next[1]:
            continue
        mrst[next[0]] = mrst[cur]+next[1]
    mmin = 1e9
    for i in range(1,node+1):
        if mrst[i] == 1e9 or visit[i]:
            continue
        elif not visit[i] and mrst[i]<mmin:
            mmin = i
    if mmin !=1e9:
        que.append(mmin)
        visit[mmin] = 1
for i in range(1,node+1):
    print(mrst[i] if mrst[i]!=1e9 else 'INF')

탐색하는데 최소 4억번의 연산이 필요해 당연히 시간초과가 났다.

그래서 최소 거리를 찾는 다익스트라 알고리즘에서 우선순위 큐는 반드시 필요한것 같다.

 

그러나 이 우선순위 큐에 익숙하지 않은 나는 heappush(거리,노드)가 아닌

heappush(노드,거리)로 해버렸다.

이렇게 되버리면 우선순위 기준을 노드숫자로 정하기에, 아무 의미가 없어진다.

결국 노드 숫자는 시작점부터 내림차순으로 진행하기에 결국 다 돌게 된다.

 

거리로 하게 되면 불필요한 연산을 막고, continue해서 시간 초과를 막을수 있었던 것이었다.

import sys
from heapq import heappush,heappop
input = sys.stdin.readline
node,edge = map(int,input().split())
start = int(input().strip())
graph = [[]for i in range(node+1)]
for i in range(edge):
    fst,scd,thd = map(int,input().split())
    graph[fst].append((scd,thd))
mrst = [1e9 for i in range(node+1)]
mrst[start] = 0
que = []
heappush(que, (mrst[start],start))
while que:
    cur = heappop(que)
    for next in graph[cur[1]]:
        new = mrst[cur[1]]+next[1]
        if mrst[next[0]]>new:
            mrst[next[0]] = new
            heappush(que,(mrst[next[0]],next[0]))
for i in range(1,node+1):
    print(mrst[i] if mrst[i]!=1e9 else 'INF')