글 읽기 - 시간초과가 왜 나는지 모르겠습니다 ㅠㅠ

jhss4475 2년 전 0

어떤 부분에서 시간초과가 날까요..?

한번 제거한거는 고려안하는 것도 그렇고, 웬만한 조건들은 전부 고려한 것 같은데 ㅠㅠㅠ

import sys
from queue import PriorityQueue
Nodeees, liness = map(int,sys.stdin.readline().split())
start_ = int(sys.stdin.readline())
fromAtoB = [[] for i in range(Nodeees+1)]
for i in range(liness):
    A,B,valuess = map(int,sys.stdin.readline().split())
    fromAtoB[A].append([B,valuess])   
for i in range(1,Nodeees+1):
    pq = PriorityQueue()
    copy_fromAtoB = fromAtoB.copy()
    pq.put((0,start_))
    while pq.empty() != True:
        gotta_getget = pq.get()
        getnode = gotta_getget[1]
        gettime = gotta_getget[0]
        if getnode == i:
            print(gettime)
            break
        try:
            for j in copy_fromAtoB[getnode]:
                pq.put((j[1]+gettime,j[0]))
            copy_fromAtoB[getnode] = 1
        except:
            pass
    else:
        print("INF") 

jhss4475 2년 전 0

저렇게 모든 i에 대해서 계속 같은 과정을 반복하며 최솟값을 구할 필요가 없었습니다 ㅠㅠㅠ

매커니즘을 한번만 반복하고 각각의 노드들 마다 최솟값을 저장해놓으면 됩니다.

예컨대 INF가 출력되는 경우에는 pq가 빌때까지 while문이 돌아가므로 무조건 INF가 출력되는걸 구하는 과정에서 모든 노드의 거리 최솟값을 구할 수 있습니다.

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

문제

문제

출처

ICPC

시간초과가 왜 나는지 모르겠습니다 ㅠㅠ

jhss4475 2년 전 0

jhss4475 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말