글 읽기 - python 다익스트라 틀렸습니다

ddrrff 2년 전 0

어느 부분에서 틀린 걸까요?

import sys
import heapq
N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
adj = [[]for _ in range(N+1)]
for _ in range(M):
    i, j, w = map(int, sys.stdin.readline().split())
    adj[i].append([w, j])
start, end = map(int, sys.stdin.readline().split())
dist = [float("INF")] * (N+1)
q = []
# when start -> start, w = 0, dist[start] = 0
heapq.heappush(q, [0, start])
dist[start] = 0
while q:
    nowCost, nowNum = heapq.heappop(q)
    for w, i in adj[nowNum]:
        if dist[nowNum] < w:
            continue
        if dist[i] > dist[nowNum] + w:
            dist[i] = dist[nowNum] + w
            heapq.heappush(q, [dist[i], i])
print(dist[end])

314programs 2년 전 1

고친 코드를 설명이랑 첨부했어요.

import sys
import heapq
N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
adj = [[]for _ in range(N+1)]
for _ in range(M):
    i, j, w = map(int, sys.stdin.readline().split())
    #i 에서 j로 가는데 드는 비용 w
    adj[i].append([j, w])
start, end = map(int, sys.stdin.readline().split())

dist = [float("INF")] * (N+1)
q = [[0, start]]
dist[start] = 0
#시작은 거리가 0

while q:
    nowCost, nowNum = heapq.heappop(q)
    
    #등록돼 있는 거리가 nowCost(지금 거리) 보다 더 작은경우 continue를 써 넘어가요.
    #이거 안하면 시간초과가 나요... 모든 경로를 채크할려면 시간이 너무 많이 걸려요
    if nowCost > dist[nowNum]:
        continue

    else:
        #지금 구한 거리에서 다른 경로들을 찾아요.
        #변수 이름이 했갈려 이름을 바꿈.
        for nextnum, nextcost in adj[nowNum]:
            #distance = 다음 숫자까지 거리
            #지금 거리와 다음 거리를 더해서 구함
            distance = nextcost + nowCost
            
            #기록된 거리보다 distance가 작을때 기록된 거리를 업대이트 하기
            if dist[nextnum] > distance:
                dist[nextnum] = distance
                heapq.heappush(q, [distance, nextnum])
print(dist[end])

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

문제

문제

출처

ICPC

python 다익스트라 틀렸습니다

ddrrff 2년 전 0

314programs 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말