글 읽기 - python 최소힙 어디서 틀렸을까요?

2wjdwo97 2년 전 0

최소힙으로 구현했는데 틀렸다고 나옵니다!

어디서 잘못된 걸까요?

from sys import stdin
import heapq
from math import inf

V, E = map(int, stdin.readline().split())
start_node = int(stdin.readline())

# 그래프 생성
graph = {}

for _ in range(V):
    u, v, w = map(int, stdin.readline().split())
    if u in graph:
        # 두 노드 사이에 edge가 여러 개 있을 수 있다고 해석해서 넣은 코드
        if v in graph[u]:
            graph[u][v] = min(graph[u][v], w)
        else:
            graph[u][v] = w
    else:
        graph[u] = {v: w}

# 시작 노드로부터의 최단 경로
distances = [inf for _ in range(V)]
distances[start_node - 1] = 0

# 최소 거리를 뽑기 위한 최소힙
h = []
heapq.heappush(h, (0, start_node))

while h:
    min_dist = heapq.heappop(h)
    cur_cost = min_dist[0]
    cur_node = min_dist[1]

    # 간선이 있다면
    if cur_node in graph:
        # 현재 노드로부터 방문할 수 있는 모든 노드 루프
        for next_node in graph[cur_node]:
            new_cost = cur_cost + graph[cur_node][next_node]
            # new cost가 더 작다면 distance 배열 업데이트, 최소힙에 push
            if distances[next_node - 1] > new_cost:
                distances[next_node - 1] = new_cost
                heapq.heappush(h, (new_cost, next_node))

for distance in distances:
    if distance == inf:
        print("INF")
    else:
        print(distance)

2wjdwo97 2년 전 0

11번째 줄 V를 E로 고쳤는데도 안 되네요 ㅠㅠ

2wjdwo97 2년 전 0

해결했습니다! V를 E로 고치면서 이상한 걸 삭제해서 안 됐었는데 다시 추가해주니까 되네요

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

문제

문제

출처

ICPC

python 최소힙 어디서 틀렸을까요?

2wjdwo97 2년 전 0

2wjdwo97 2년 전 0

2wjdwo97 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말