글 읽기 - [파이썬] 13% 쯤에서 틀렸다고 뜨는데 이유를 모르겠습니다.

zxc715169 2년 전 2

혹시 반례가 있을까요? ..

import sys
import heapq
input = sys.stdin.readline

def dijkstra(graph,start):
    distances[start] = 0 
    queue = [] 
    heapq.heappush(queue, [distances[start], start])

    while queue:
        current_distance, current_destination = heapq.heappop(queue)
        if current_distance > distances[current_destination]:
            continue

        for new_destination, new_distance in graph[current_destination].items():
            distance = current_distance + new_distance
            if distance < distances[new_destination]:
                distances[new_destination] = distance
                heapq.heappush(queue, [distance, new_destination])

v, e = map(int,input().split())
k = int(input()) 
graph= dict()
for i in range(1,v+1):
    graph[i] = {}

for i in range(e):
    v1, v2, weight = map(int,input().split())
    graph[v1][v2] = weight 

distances = {node: float('inf') for node in graph}
dijkstra(graph,k)
for key, value in distances.items():
    if value == float('inf'):
        print('INF')
    else:
        print(value)

jeonggu223 2년 전 3

서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

dict형식으로 받아 생기는 반례가 있을 것 같네요.

zxc715169 2년 전 1

리스트로 바꿔서 입력 받아보니 작동하네요. 정말 감사합니다 !!

lima36 1년 전 0

생각해보니 맞네요. 같은 노드에 중복적으로 추가되는 경우가 있는데 dictionary하게 되면 이전값이 사라지게 되니..

defaultdict(list)로 수정하니, 13%에서 지나갑니다.

감사합니다.

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

문제

문제

출처

ICPC

[파이썬] 13% 쯤에서 틀렸다고 뜨는데 이유를 모르겠습니다.

zxc715169 2년 전 2

jeonggu223 2년 전 3

zxc715169 2년 전 1

lima36 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말