글 읽기 - 1005번 문제 파이썬 코드 시간초과가 납니다.

mycool0905 5년 전 0

예시 넣었을 때, 답이 잘 나오는데 다른 반례 넣었을 때 시간초과가 나는듯하네요..

혹시 뭐가 문제인지 알려주실 수 있나요?

from collections import deque

def topSort(graph,D,indegree,W):
    queue = deque()
    temp = {}
    for i in graph:
        temp[i] = 0

    for i in graph:
        if indegree[i] == 0:
            queue.append(i)
            indegree.pop(i)
            temp[i] = D[i]
                
    while len(queue) != 0:
        u = queue.popleft()
        if u == W:
            return temp[u]

        for i in graph[u]:
            indegree[i] -= 1
            temp[i] = max(temp[i],temp[u]+D[i])
            if indegree[i] == 0:
                queue.append(i)
                indegree.pop(i)

#메인
for t in range(int(input())):
    N,K = map(int,input().split())
    D = tuple(map(int,input().split()))
    graph = {}
    indegree = {}
    for i in range(N):
        graph[i] = []
        indegree[i] = 0
    for i in range(K):
        X,Y = map(int,input().split())
        graph[X-1].append(Y-1)
        indegree[Y-1] += 1
    W = int(input())
    W -= 1
    print(topSort(graph,D,indegree,W))

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

문제

문제

출처

ICPC

1005번 문제 파이썬 코드 시간초과가 납니다.

mycool0905 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말