글 읽기 - 파이썬 왜 시간초과가 날까요..??

ifiwere 2년 전 0

다익스트라 제대로 쓴거같은데... 30%에서 시간초과가 나옵니다.

import sys
import heapq
input = sys.stdin.readline
n = int(input())
m = int(input())
graph = {}
for i in range(m):
    a,b,c = map(int,input().split())
    graph[a] = graph.get(a,[]) + [[b,c]]
s,t = map(int, input().split())

visited = [False for _ in range(n+1)]
move = [0 for _ in range(n+1)]
dist = [sys.maxsize for _ in range(n+1)]
dist[s] = 0

Q = [[0,s]]
while Q:
    total, now = heapq.heappop(Q)
    if not visited[now]:
        visited[now] = True
        for next, cost in graph.get(now,[]):
            if dist[next]>total+cost:
                dist[next] = total+cost
                move[next] = now
                heapq.heappush(Q,[dist[next],next])

print(dist[t])
tmp = t
route = []
while tmp:
    route.append(tmp)
    tmp = move[tmp]
print(len(route))
print(' '.join(map(str,route[::-1])))

ifiwere 2년 전 0

graph를 딕셔너리를 안쓰고 리스트로 하니 통과되네요. 역시 키가 너무많아지면 찾는데 시간이 많이걸리나 봅니다.

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

문제

문제

출처

ICPC

파이썬 왜 시간초과가 날까요..??

ifiwere 2년 전 0

ifiwere 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말