글 읽기 - 파이썬) 시간초과 질문입니다.

jckim0307 2년 전 0

시간을 최대한 줄여보려고 여러 방법을 써봤지만, 57%에서 계속 시간초과가 납니다. 어떻게 하면 시간을 더 줄일 수 있을까요?

import sys
n, m, q = map(int, sys.stdin.readline().rstrip().split())
inf = 10001
dog = list(map(int, sys.stdin.readline().rstrip().split()))
data = [[[inf, max(dog[i], dog[j])] for j in range(n)] for i in range(n)]

for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().rstrip().split())
    a -= 1
    b -= 1
    data[a][b][0] = data[b][a][0] = c

dog = sorted([(dog[i], i) for i in range(n)], key=lambda x: x[0])
for d in dog:
    k = d[1]
    for a in range(n):
        for b in range(a + 1, n):
            s = max(data[a][b][1], d[0])
            check1, check2 = data[a][b][0] + data[a][b][1], data[a][k][0] + data[k][b][0] + s
            if check1 > check2:
                data[a][b][0] = data[b][a][0] = data[a][k][0] + data[k][b][0]
                data[a][b][1] = data[b][a][1] = s

for _ in range(q):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    a -= 1
    b -= 1
    if data[a][b][0] == inf:
        sys.stdout.write('-1\n')
    else:
        sys.stdout.write(str(data[a][b][0] + data[a][b][1]) + '\n')

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

문제

문제

출처

ICPC

파이썬) 시간초과 질문입니다.

jckim0307 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말