글 읽기 - 오류인건지 pypy 컴파일러 문제인건지 확인부탁드립니다.

jeongtai 2년 전 0

문제에서 분명히 1부터 시작이라고해서 17,18번째 줄에 1을 넣어서 돌렸습니다.

하지만 틀렸다고 나왔고 51번째 줄처럼 함수형으로 바꿔서 풀었더니 맞았다고 나옵니다.

결과는 똑같다고 생각하는데 뭐 때문에 틀렸는지 확인 부탁드려도 될까요?

#틀린 코드
import heapq

n, m, k = map(int, input().split())
List = [[] for _ in range(n+1)]
#k번까지 포장할 수 있으니 k+1만큼 이차원 배열 생성
dist = [[float('inf')]*(k+1) for _ in range(n+1)]
#양방향으로 노드간 거리 생성
for _ in range(m):
    s, e, w = map(int, input().split())
    List[s].append((w, e))
    List[e].append((w, s))

hq = []
# 1에서 1로 가는데 0번 포장했을 경우 = 0
for i in range(k+1):
    dist[1][i] = 0
heapq.heappush(hq, (0, 0, 1))
while hq:
    #가중치, 포장 횟수, 노드
    w, k_cnt, n = heapq.heappop(hq)
    if dist[n][k_cnt] < w:
        continue
    
    #노드가 이어진 곳들 탐색
    for tw, tn in List[n]:
        if k_cnt < k:
            if dist[tn][k_cnt+1] > w:
                dist[tn][k_cnt+1] = w
                heapq.heappush(hq, (w, k_cnt+1, tn))
            
        cost = w + tw
        if dist[tn][k_cnt] > cost:
            dist[tn][k_cnt] = cost
            heapq.heappush(hq, (cost, k_cnt, tn))
print(min(dist[n]))
#######################################################################
#맞은코드
import heapq

n, m, k = map(int, input().split())
List = [[] for _ in range(n+1)]
#k번까지 포장할 수 있으니 k+1만큼 이차원 배열 생성
dist = [[float('inf')]*(k+1) for _ in range(n+1)]
#양방향으로 노드간 거리 생성
for _ in range(m):
    s, e, w = map(int, input().split())
    List[s].append((w, e))
    List[e].append((w, s))

#여기를 함수화 했더니 맞음
def dj(start):
    hq = []
    # 1에서 1로 가는데 0번 포장했을 경우 = 0
    for i in range(k+1):
        dist[start][i] = 0
    heapq.heappush(hq, (0, 0, start))
    while hq:
        #가중치, 포장 횟수, 노드
        w, k_cnt, n = heapq.heappop(hq)
        if dist[n][k_cnt] < w:
            continue
        
        #노드가 이어진 곳들 탐색
        for tw, tn in List[n]:
            if k_cnt < k:
                if dist[tn][k_cnt+1] > w:
                    dist[tn][k_cnt+1] = w
                    heapq.heappush(hq, (w, k_cnt+1, tn))
                
            cost = w + tw
            if dist[tn][k_cnt] > cost:
                dist[tn][k_cnt] = cost
                heapq.heappush(hq, (cost, k_cnt, tn))
dj(1)
print(min(dist[n]))

djm03178 2년 전 1

루프 내에서 쓰이는 n이 루프 밖에서의 n을 덮어쓰고 있어 마지막 출력시의 n도 바뀌게 됩니다.

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

문제

문제

출처

ICPC

오류인건지 pypy 컴파일러 문제인건지 확인부탁드립니다.

jeongtai 2년 전 0

djm03178 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말