글 읽기 - [파이썬 3] 시간초과 질문입니다.!

vitriol95 3년 전 0

45%에서 시간초과 오류가 뜨네요... if ~ in 문(20line)에서 오류가 있는걸까요? 계속 생각해봐도 안나와서 이렇게 도움 청합니다 ㅠ

import heapq
import sys
input = sys.stdin.readline
INF = 1e9

def new_dijk():
    distance = [INF]*(n+1)
    distance[1] = 0
    q = []
    heapq.heappush(q,[0,[1]])

    while q:
        dist, path = heapq.heappop(q)
        now = path[-1]

        if distance[now] >= dist:
            for next in graph[now]:
                cost = dist + next[0]
                if distance[next[1]] > cost:
                    if next[1] in path:
                        return False
                    distance[next[1]] = cost
                    heapq.heappush(q, [cost,path+[next[1]]])

    return distance

n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    s, e, t = map(int, input().split())
    graph[s].append([t,e])

result = new_dijk()
if result:
    for i in range(2,n+1):
        if result[i] == INF:
            print(-1)
        else: print(result[i])

else:
    print(-1)

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

문제

문제

출처

ICPC

[파이썬 3] 시간초과 질문입니다.!

vitriol95 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말