글 읽기 - [python3] [다익스트라] 반례를 못찾는 것일까요?

smyf201 2년 전 0

질문게시판에 있는 반례들을 적용해봐도 틀렸다고 뜹니다..

도와주시면 감사하겠습니다!!

import heapq 
import sys
input = sys.stdin.readline
INF = sys.maxsize

n, m, goal = map(int, input().split())
graph = [[] for _ in range(n+1)] # graph = [[]]
for _ in range(m):
    u, v, w = map(int, input().split())
    graph[u].append((v,w))

def dijkstra(start, goal):
    q = []
    distance = [INF]*(n+1)
    heapq.heappush(q, (0, start)) 
    # 거리 우선순위 큐 : 튜플은 앞에 있는 원소 순서대로 비교하므로 (거리, 위치) 순서!
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist :
            continue
        for next, d in graph[now]:
            if dist + d < distance[next] : 
                distance[next] = dist + d
                heapq.heappush(q, (distance[next], next)) 
                
    return distance[goal]

menu = 0
for i in range(1,n+1):
    menu = max( dijkstra(i, goal) + dijkstra(goal, i), menu)

print(menu)

lcr7324 2년 전 2

dijkstra(goal, goal) * 2가 정답보다 큰 경우가 있을 수 있습니다.

29~30번 줄의 for문에서 i == goal일 때를 건너뛰도록 하면 통과입니다.

smyf201 2년 전 1

dijkstra(goal, goal) = 0 일거라 생각했던게 오류네요 ...!!! 정말 감사합니다

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

문제

문제

출처

ICPC

[python3] [다익스트라] 반례를 못찾는 것일까요?

smyf201 2년 전 0

lcr7324 2년 전 2

smyf201 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말