글 읽기 - 파이썬으로 통과하신분 있나요

forybm 6년 전 0

항상 c++로만 짜다가 파이썬으로 다시 풀어보고 있는데

간단하게 priority queue 로 짜봤습니다.

그런데 시간초과가 나네요 !! 혹시 제가 잘못 구현한건지 아니면 파이썬의 속도가 느려서

시간 초과가 난건지 궁금합니다!!

import queue

info = input().split(" ")
V = int(info[0])
E = int(info[1])
S = int(input())

arr = [[] for i in range(V+1)]
node = [ 987654321 for i in range(V+1)]
node[S] = 0

pq = queue.PriorityQueue()

for i in range(E):
    info = input().split(" ")
    x = int(info[0])
    y = int(info[1])
    w = int(info[2])
    arr[x].append([y,w])

pq.put([node[S], S])

while not pq.empty():
    dist, u = pq.get()
    
    for item in arr[now[1]]:
        v = item[0]
        weight = item[1]
        if node[v] > dist + weight:
            node[v] = dist + weight
            pq.put([node[v], v])

for i in range(1, V+1):
    if node[i] != 987654321:
        print(node[i])
    else:
        print("INF")

jh05013 6년 전 1

input은 굉장히 느립니다. 입력이 몇 만 줄 이상 되면 sys.stdin.readline을 써야 합니다.

forybm 6년 전 0

아하 그렇군요.. 감사합니다!!

sait2000 6년 전 0

사실 Python 2를 쓴다면 PyPy를 쓸 수도 있습니다. 이상하게 PyPy에선 input()이 안 느립니다. 이유는 모르겠습니다.

PyPy3은 제가 잘 안 써봐서 모르겠네요. 만약에 쓰실 일이 있으면 PyPy3 5.5.0은 Python 3.3.5하고 호환되는 버전이라는 거 주의하셔야 할 걸요.

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

문제

문제

출처

ICPC

파이썬으로 통과하신분 있나요

forybm 6년 전 0

jh05013 6년 전 1

forybm 6년 전 0

sait2000 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말