글 읽기 - 파이썬 고수님들 질문드려요!

omy5123 3년 전 0

시간 초과가 나왔는데,, 일단 예제는 맞게 나오는데 이렇게 접근하는게 맞나 싶어요! 혹시 맞으면 시간초과를 어떻게 줄일수 있을까요,, 혹시 반례도 있으면 부탁드립니다.

import sys
from collections import deque
from heapq import heappush,heappop
def dijkstra(start,s):    #최단경로 찾기
    heap = []
    dp = [inf for i in range(n+1)]
    dp[start] = 0
    heappush(heap, [0, start])
    while heap:
        a, b = heappop(heap)
        for n_n, wei in s[b]:
            n_w = a + wei
            if dp[n_n] > n_w and check[b][n_n] == 0:
                dp[n_n] = n_w
                heappush(heap, [n_w, n_n])
    return dp

def delete(end,dp):    #역추적으로 가장 최단경로 삭제
    q = deque()
    q.append(end)
    while q:
        num = q.popleft()
        for a,b in arr_1[num]:
            if dp[num] == dp[a]+b:
                check[a][num] = 1
                q.append(a)

n,m,k = map(int,input().split())
inf = sys.maxsize
arr = [[] for _ in range(n+1)]
arr_1 = [[] for _ in range(n+1)]
check = [[0] * (n+1) for i in range(n+1)]
for _ in range(m):
    a,b,c = map(int,input().split())
    arr[a].append([b,c])
    arr_1[b].append([a,c])
for i in range(1,n+1):
    dp = dijkstra(1,arr)
    for j in range(1,k):    #k-1 번만큼 최단경로 삭제해주고 밑에서 프린트
        delete(i,dp)
        dp = dijkstra(1, arr)
    check = [[0] * (n + 1) for _ in range(n + 1)]
    if dp[i] == 0:
        print(-1)
    else:
        print(dp[i])

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

문제

문제

출처

ICPC

파이썬 고수님들 질문드려요!

omy5123 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말