글 읽기 - heapq와 PriorityQueue 속도차이가 있나요..?

ntommy11 3년 전 0

검색해보니까 PriorityQueue는 내부적으로 heapq를 쓴다는데,

같은 코드인데 heapq면 통과하고 PriorityQueue쓰면 시간이 초과되네요ㅜㅠ 이유가 궁금합니다..

from queue import PriorityQueue
N, M, X = map(int, input().split())

INF = float('inf')
def dijkstra(N,x):
    dist = [INF]*N
    dist[x]=0
    pq = PriorityQueue()
    pq.put((0,x))
    
    while not pq.empty():
        cost, i = pq.get()
        
        for j, t in adj[i]:
            t += cost
            if t < dist[j]:
                dist[j] = t
                pq.put((t, j))
    return dist
    
    
adj = [[] for _ in range(N)]
ans = [0]*N
for _ in range(M):
    u,v,t = map(int, input().split())
    adj[u-1].append((v-1,t))
    
for i in range(N):
    ret = dijkstra(N,i)
    
    if i==X-1:
        for j, t in enumerate(ret):
            ans[j] += t
    else:
        ans[i] += ret[X-1]
print(max(ans))

shg9411 3년 전 0

queue는 동기화를 지원해서 느립니다.

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

문제

문제

출처

ICPC

heapq와 PriorityQueue 속도차이가 있나요..?

ntommy11 3년 전 0

shg9411 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말