글 읽기 - 1005번 문제 파이썬 코드 시간초과 납니다. 도와주세요 ㅠㅠ

mycool0905 5년 전 0

이게.. 문제 예시로는 풀리는데 무슨 반례가 있어서 그런지 시간 초과가 발생하네요..

14%쯤에서 부터 안오르던데 왜 이럴까요..

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)
            temp[i] = D[i]
                
    for t in graph:
        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)

#메인
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))

ploffer11 5년 전 1

fast io 안하고 pypy3만 해도 2000ms대로 통과하네요.

python 3는 느립니다.

mycool0905 5년 전 0

아 감사합니다!

근데 fast io는 뭔가요?

ploffer11 5년 전 2

파이썬의 input()이나 print()는 느립니다.

import sys를 한 후

sys.stdin.readline()과

sys.stdout.write()함수를 사용하면 2000ms에서 900ms까지 줄어듭니다.

10만개 이상의 input일 땐 fast io를 사용하는 게 좋습니다.

mycool0905 5년 전 0

와 이런게 있었네요..!

좋은 정보 감사합니다!!^.^

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

문제

문제

출처

ICPC

1005번 문제 파이썬 코드 시간초과 납니다. 도와주세요 ㅠㅠ

mycool0905 5년 전 0

ploffer11 5년 전 1

mycool0905 5년 전 0

ploffer11 5년 전 2

mycool0905 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말