글 읽기 - [10217번] KCM Travel 다익스트라 파이썬 어디가 틀렸을까요...

2wjdwo97 2년 전 0

다익스트라 + dp로 풀이했고 자꾸 틀렸습니다가 나옵니다

어디가 틀린 건가요?

from sys import stdin
import heapq
from math import inf

for _ in range(int(stdin.readline())):
    graph = {}
    V, M, E = map(int, stdin.readline().split())
    
    # 그래프 초기화
    for _ in range(E):
        u, v, c, d = map(int, stdin.readline().split())
        if u in graph:
            graph[u][v] = (d, c)
        else:
            graph[u] = {v: (d, c)}

    # dp table  distances[node_num][cost] = dist
    distances = [[inf for _ in range(M + 1)] for _ in range(V)]
    distances[0][0] = 0

    h = []
    heapq.heappush(h, (0, 0, 1))  # (dist, cost, node)
    ans = inf
    
    # Dijkstra
    while h:
        # 우선순위 dist 로 pop
        cur_dist, cur_cost, cur_node = heapq.heappop(h)
        
        # 현재 노드가 목적지인 경우 break
        if cur_node == V:
            ans = cur_dist
            break
        if cur_node in graph:
            # 이웃 노드 순회
            for next_node in graph[cur_node]:
                # 이웃 노드의 거리랑 비용 계산
                new_dist = distances[cur_node - 1][cur_cost] + graph[cur_node][next_node][0]
                new_cost = cur_cost + graph[cur_node][next_node][1]
                
                # 비용이 예산보다 작고 거리가 dp 값보다 짧다면
                if new_cost <= M and new_dist <= distances[next_node - 1][new_cost]:
                    # dp 업데이트, 우선순위 큐에 push
                    distances[next_node - 1][new_cost] = new_dist
                    heapq.heappush(h, (new_dist, new_cost, next_node))

    print(ans if ans != inf else "Poor KCM")

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

문제

문제

출처

ICPC

[10217번] KCM Travel 다익스트라 파이썬 어디가 틀렸을까요...

2wjdwo97 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말