글 읽기 - 파이썬_벨만-포드를 이해하고 다익스트라 응용해보기

grasshoppertrainer 3년 전 1

벨만-포드를 읽고 다익스트라 코딩 패턴을 이용해 풀어보려고 했습니다.

노드 별로 갱신 횟수를 저장하고 갱신 횟수가 N(노드 수) - 1 보다 크면 싸이클을 감지하고 종료하는 방법입니다.

그런데 43%에서 틀렸다고 나오네요.

'출력 초과'가 아닌 '틀렸습니다'가 출력되는 바 싸이클이 없는데 싸이클이 있다고, 즉 k 개의 답을 출력해야 하는데 -1을 출력하고 있는것 아닌가 하는 생각이 듭니다.

논리적으로 잘못된 부분을 못찾겠어서 흥미롭습니다.

반례를 제시해주시거나 틀린 부분을 지적해주시면 감사하겠습니다.

from sys import stdin
import heapq
from math import inf, isinf


def solution(N, edges):
    tree = {}
    for s, e, c in edges:
        # !KILLER CASE! for implicit description
        # almost always use this pattern to store best out of duplicate
        d = tree.setdefault(s, {})
        d[e] = min([d.get(e, inf), c])

    costs = {i: [inf, 0] for i in range(1, N+1)}    # {idx: [cost, renewal count]}
    costs[1] = [0, 0]
    heap = [(0, 1)]

    while heap:
        _, node = heapq.heappop(heap)

        for next_node, time in tree.get(node, {}).items():
            if costs[next_node][0] > costs[node][0] + time:
                # max renewal count in N-1
                # trying one more time means a loop!
                if costs[next_node][1] == N:
                    return [-1]
                costs[next_node][1] += 1

                costs[next_node][0] = costs[node][0] + time
                heapq.heappush(heap, (costs[next_node][0], next_node))

    result = []
    for i in range(2, N+1):
        if isinf(costs[i][0]):
            result.append(-1)
        else:
            result.append(costs[i][0])
    return result


N, M, edges = 0, 0, []
for i, row in enumerate(stdin.readlines()):
    row = [int(c) for c in row.strip().split(' ')]
    if i == 0:
        N, M = row
    else:
        edges.append(row)

for a in solution(N, edges):
    print(a)

sylee0802 2년 전 0

저도 벨만 포드 알고리즘을 모르는 상태에서 다익스트라로 풀기 위해 이와 유사한 코드를 작성했습니다.

혹시 왜 다익스트라로 풀면 오류가 나는지 원인을 알게 되셨습니까?

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

문제

문제

출처

ICPC

파이썬_벨만-포드를 이해하고 다익스트라 응용해보기

grasshoppertrainer 3년 전 1

sylee0802 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말