글 읽기 - [파이썬] 기존 다익스트라에다가 카운트를 붙이면 안되는 걸까요?

h2j4607 2년 전 0

다익스트라를 공부한 후 벨만포드 문제를 진행 중에 있습니다.

기존 다익스트라에서 카운터 변수를 추가하였습니다.
카운터는 최단거리가 업데이트할때마다 +1 하였습니다.

그리고 카운터가 기존 노드 수 이상이면 False를 출력하게 하였는데, 에러가 발생합니다.

어느 부분에서 수정이 필요한지, 틀린 개념이 무엇인지 알려주시면 감사하겠습니다.

import sys
import heapq

N, M = map(int, sys.stdin.readline().split())
graph_list = [[] for _ in range(N+1)]

for _ in range(M):
    A, B, C = map(int, sys.stdin.readline().split())
    graph_list[A].append((B, C))

INF = sys.maxsize

def belman_ford(graph):
    dp = [INF for _ in range(N + 1)]
    dp[1] = 0
    heap = []
    heapq.heappush(heap, (0, 1))
    cnt = 0
    while heap:
        weight, node = heapq.heappop(heap)
        
        # 카운트가 노드의 갯수 보다 많을 경우 음의 반복으로 False
        if cnt > N:
            return False

        if dp[node] < weight:
            continue
            
        for find_node, find_weight in graph[node]:
            sum_weight = find_weight + weight
            
            if sum_weight < dp[find_node]:
                # 노드를 방문할때마다 cnt 업데이트
                cnt += 1
                dp[find_node] = sum_weight
                heapq.heappush(heap, (find_weight, find_node))
    
    return dp[2:]

result = belman_ford(graph_list)
print(result)

if not result:
    print(-1)
else:
    for i in result:
        if i >= INF:
            print(-1)
        else:
            print(i)

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

문제

문제

출처

ICPC

[파이썬] 기존 다익스트라에다가 카운트를 붙이면 안되는 걸까요?

h2j4607 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말