글 읽기 - 같은 코드 같은데 하나는 정답 하나는 오답이라고 합니다 ㅠㅠ

tjatn304905 2년 전 0

두 개의 코드를 실행해 보았는데, 아래의 코드는 오답이라고 나옵니다.

위의 코드와 전체적으로 구조는 똑같고, 변수명과 선언 순서정도만 다른데, 왜 그런지 도저히 모르겠습니다 ㅠㅠ.

고수분들 보고 도와주시면 감사하겠습니다!

# (정답코드)

import sys
from heapq import heappop, heappush

INF = int(1e9)

input = sys.stdin.readline

N = int(input())
M = int(input())

graph = [[] for _ in range(N+1)]
for _ in range(M):
    s, e, c = map(int, input().split())
    graph[s].append((e, c))

start, end = map(int, input().split())

def dijkstar(start, end):
    distance = [INF] * (N+1)
    distance[start] = 0

    q = []
    heappush(q, (0, start))

    while q:
        dist, now = heappop(q)

        if distance[now] < dist:
            continue

        for node, cost in graph[now]:
            cost += dist

            if distance[node] > cost:
                distance[node] = cost
                heappush(q, (cost, node))

    return distance[end]

print(dijkstar(start, end))

##########################################################################
# (오답코드)

import sys
from heapq import heappush, heappop

input = sys.stdin.readline

N = int(input())  # 도시의 개수
M = int(input())  # 버스의 개수

cities = [[] for _ in range(N+1)]  # 도시 간 비용을 나타내는 2차원 리스트

# 버스정보: 시작지, 도착지, 요금 입력
for i in range(M):
    s, e, c = map(int, input().split())
    cities[s].append((e, c))

start, end = map(int, input().split())  # 출발점, 도착점

INF = float('inf')

# start에서 특정 도시까지 가는데 걸리는 최소한의 비용
min_cost = [INF for _ in range(N+1)]
min_cost[start] = 0

hq = []  # 힙큐
heappush(hq, (0, start))

while hq:
    cost, current = heappop(hq)

    # 현재 구한 비용이 더 적으면 그냥 넘어가기
    if min_cost[current] < cost:
        continue

    # 현재 노드를 순회하면서 거쳐가기
    for node, node_cost in cities[current]:
        if min_cost[node] > node_cost + cost:  # 최소 비용보다 지금 구한 비용이 더 적으면 교체
            min_cost[node] = node_cost + cost
            heappush(hq, (node_cost, node))  # 그 노드를 거쳐 가는 버스노선들 추가

print(min_cost[end])

choijy9943 2년 전 0

line 84 에 node_cost 값이 업데이트가 안되서 무한룹이네용

node_cost+cost로 바꾸시면 해결될거같습니다

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

문제

문제

출처

ICPC

같은 코드 같은데 하나는 정답 하나는 오답이라고 합니다 ㅠㅠ

tjatn304905 2년 전 0

choijy9943 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말