[Python] 1753번 최단경로

import sys,heapq
input=sys.stdin.readline

def dijkstra(start):
    hq=[]
    heapq.heappush(hq,(0,start)) # heapq는 첫번째 요소를 기준으로 최솟값 꺼냄!!!
    dist[start]=0

    while hq:
        d,u=heapq.heappop(hq)

        if dist[u]<d:
            continue

        for v,w in edges[u]:
            nw=d+w
            if dist[v]>nw:
                dist[v]=nw
                heapq.heappush(hq,(nw,v))

#1.입력
V,E=map(int,input().split())
start=int(input())

#2.자료형 정의
INF=float('inf')
edges=[[] for _ in range(V+1)]
dist=[INF for _ in range(V+1)]

for _ in range(E):
    u,v,w=map(int,input().split())
    edges[u].append((v,w))

#3.동작 알고리즘
dijkstra(start)

#4.출력
for i in range(1,V+1):
    if dist[i]==INF:
        dist[i]='INF'
    print(dist[i])

코드를 맞기까지 정말 많이 틀렸었다.

다익스트라 개념도 다시 복습하고, 확인했는데도 계속 틀리길래 미쳐버릴 것 같아 결국 GPT햄의 도움을 받았다.

내가 했던 가장 큰 실수는 파이썬의 heapq는 첫 번째 원소를 기준으로 최소값을 꺼낸다는 것이였다.

내가 계속했던 실수는 heapq를 (노드,거리)로 저장하고 빼내고 있어서 노드 기준으로 최솟값이 정렬되었기 때문에 계속 시간 초과가 발생했던 것이다. (거리,노드)로 heapq를 짜니 바로 통과하였다. 30분 동안 고민했던 것이 너무 간단한거였어서,,, 정답을 알고나니 어이가 없었다...

수많은 시도 끝에 드디어 성공...

 

 

그리고 tmi는....

백준 계정을 새로 팠다.

새로운 계정으로 플레까지 도전해볼려고한다.

알고리즘 고수가 될테야.