글 읽기 - 시간초과

boompatron 1년 전 0

알고리즘도 맞고 시간 복잡도도 그렇고 맞는 것 같은데 왜 시간 초과가 날까요... 질문 게시판에 저랑 비슷하게 구현하신 분도 계신대..
지적 부탁드립니다...

import sys
INF = 123456789


def floyd_warshall(g, v):
    for k in range(1, v + 1):
        for i in range(1, v + 1):
            for j in range(1, v + 1):
                g[i][j] = min(g[i][j], g[i][k] + g[k][j])


def solution():
    v, e = map(int, sys.stdin.readline().rstrip().split())
    g, ans = [[INF for _ in range(v + 1)] for __ in range(v + 1)], INF
    for i in range(1, v + 1):
        g[i][i] = 0
    for i in range(e):
        a, b, c = map(int, sys.stdin.readline().rstrip().split())
        g[a][b] = c
    floyd_warshall(g, v)
    for i in range(1, v + 1):
        for j in range(i + 1, v + 1):
            ans = min(ans, g[i][j] + g[j][i])
    print(ans if ans != INF else -1)


if __name__ == "__main__":
    solution()

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

문제

문제

출처

ICPC

시간초과

boompatron 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말