글 읽기 - 파이썬 시간초과 코드 차이점이 궁금합니다.

woghdclf 2년 전 0

heappush와 heappop에 데이터를 넣는 순서에 따라 시간 초과가 발생합니다.

17, 21, 28 번 라인에 노드와 거리(비용) push, pop 순서를 다음과 같이 바꿔주면 시간초과가 발생합니다.

17 - heapq.heappush(q,(S,0))

21 - now, co = heapq.heappop(q)

28 - heapq.heappush(q,(i[0], cost))

반대로 다시 바꿔주면 정답처리가 되는데 이유가 궁금합니다.

import heapq
import sys
input = sys.stdin.readline

V, E = map(int,input().split())
S = int(input())
INF = int(1e9)
data = [[] for _ in range(V+1)]
distance = [INF] * (V+1)

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


q = []
heapq.heappush(q,(0,S))
distance[S] = 0

while q:
    co, now = heapq.heappop(q)
    if distance[now] < co:
        continue
    for i in data[now]: #i[0] 도착, i[1] 비용
        cost = i[1] + co
        if distance[i[0]] > cost:
            distance[i[0]] = cost
            heapq.heappush(q,(cost, i[0]))

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

choko100 2년 전 0

안녕하세요, Python 의 heapq 는 첫번째 요소를 기준으로 정렬합니다.

cost 를 기준으로 heapq를 구성해야하기 때문에, cost 가 맨 앞에 와야 맞습니다!

(그렇지 않은 경우, heap 이 제대로 구성되지 않아 우선순위를 이용해 빠르게 끝나지 못하고 모든 경우를 다 돌기 때문에 시간 안에 들어올 수가 없습니다)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

파이썬 시간초과 코드 차이점이 궁금합니다.

woghdclf 2년 전 0

choko100 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말