글 읽기 - 다익스트라로 풀어보았는데 정답은 잘 출력되는데 계속 틀리네요..

miseongk 1년 전 1

안녕하세요

다익스트라로 풀어보았는데 혹시 반례 찾아주실수 있을까요ㅠㅠ

처음에 런타임 에러 뜨다가 그래프에 추가하는 범위를 100001로 바꿔주니까 이제 런타임에러는 안뜨고 틀렸다고 나오네요..

import heapq
import sys
INF = int(1e9)

n, k = map(int, input().split())
graph = [[] for _ in range(200001)]
d = [INF] * 200001

for i in range(1, 100001):
    graph[i].append((i * 2, 0))
    graph[i].append((i - 1, 1))
    graph[i].append((i + 1, 1))


if n == 0:
    if k == n:
        print(0)
    else:
        print(1)
    exit(0)

q = []
d[n] = 0
heapq.heappush(q, (0, n))
while q:
    dist, now = heapq.heappop(q)
    if dist > d[now]:
        continue
    for i in graph[now]:
        cost = dist + i[1]
        if cost < d[i[0]]:
            d[i[0]] = cost
            heapq.heappush(q, (cost, i[0]))

print(d[k])

sjm1309 1년 전 0

n 이 0일 때 m이 다른 숫자가 나오면 0이나 1이 아닌 다른 값도 나올 수 있습니다.

Input : 0 5

Answer: 2

Input : 0 17

Answer: 2

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

문제

문제

출처

ICPC

다익스트라로 풀어보았는데 정답은 잘 출력되는데 계속 틀리네요..

miseongk 1년 전 1

sjm1309 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말