글 읽기 - 파이썬 37%에서 틀렸습니다가 나옵니다.

pepper_mis 3년 전 0

문제에 있는거랑, 제가 따로 만든 테스트 케이스 만들어서 넣어봤는데 다 잘 돌아갔어요..

37%에서 '틀렸습니다'가 뜨는데 어디가 잘못된건지 알 수 있을까요? 저는 시간초과가 뜰줄 알았거든요..()

아니면 반례를 알 수 있을까요?

import sys
import heapq
#input = sys.stdin.readline
INF = sys.maxsize

T = int(input())
for t in range(T):
    N, M, K = map(int, input().split()) #공항의 수N, 총 지원비용 M, 티켓정보 수 K
    graph = [[] for i in range(N + 1)]
    for k in range(K):
        u, v, c, d = map(int, input().split()) #출발, 도착, 비용, 시간
        graph[u].append([v, c, d])

    def Dijkstra(cost):
        result = [[INF, INF] for i in range(N+1)] #시간, 비용
        heap = []
        result[1] = [0, 0]
        heapq.heappush(heap, (0, 1)) #시간, 노드

        while heap:
            w, v = heapq.heappop(heap)

            if result[v][0] < w:
                continue

            for nn , nc, nw in graph[v]: #nn: 다음 노드, nc:비용, nw: 시간
                next_w = nw + w
                total_cost = nc + result[v][1]
                if next_w < result[nn][0] and cost>=total_cost:
                    result[nn] = [next_w, total_cost]
                    heapq.heappush(heap, (next_w, nn))

        if cost != 1:
            for i in range(1, N+1):
                if result[i][0] > dp[cost-1][i][0]:
                    result[i][0] = dp[cost-1][i][0]
                    result[i][1] = dp[cost-1][i][1]

        return result

    dp = [[] for i in range(M+1)]
    for i in range(1, M+1):
        dp[i]=Dijkstra(i)

    if dp[-1][-1][0] == INF:
        print("Poor KCM")
    else:
        print(dp[-1][-1][0])

kth990303 3년 전 6

반례 드립니다

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

문제

문제

출처

ICPC

파이썬 37%에서 틀렸습니다가 나옵니다.

pepper_mis 3년 전 0

kth990303 3년 전 6

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말