1753 최단경로 python

https://www.acmicpc.net/problem/1753

1753번: 최단경로

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 접근

다익스트라 알고리즘

 

필요한 변수

-변수-
dp: 최종 비용을 저장해둠
heap: 가중치를 계산하기위해 사용하는 힙
graph: 입력으로 주어지는 그래프를 저장 [다음 노드, 다음 가중치]

https://namu.wiki/w/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

다익스트라 알고리즘 - 나무위키

https://ko.wikipedia.org/wiki/%EB%8D%B0%EC%9D%B4%ED%81%AC%EC%8A%A4%ED%8A%B8%EB%9D%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

데이크스트라 알고리즘 - 위키백과, 우리 모두의 백과사전

모든 경로의 최단경로를 파악하는 알고리즘.

꺼무위키나 위키피디아를 보면 이해하기쉽고 처음 풀땐 코드먼저 보면서 풀었다.

 

 

 

 

엄청나게 틀렸는데, heap에 저장할때 (가중치, 다음노드)로 저장해야하는데 (다음노드, 가중치)로 저장했다가 시간초과로 엄청 틀렸다.

이게 왜 틀린지 몰라서 머리가 엄청 아팠는데.... 너무나도 당연했다.

(다음노드, 가중치)순으로 heap에 저장하면 매번 heap을 찾을때 마다 다음노드를 먼저보고 같으니 가중치로 넘어가게된다...

처음부터 가중치를 먼저 확인하면 시간이 훨씬 줄어드니 당연한 사실이였다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

틀린 코드

import heapq
import sys
input = sys.stdin.readline

"""
다익스트라 알고리즘

-변수-
dp: 최종 비용을 저장해둠
heap: 가중치를 계산하기위해 사용하는 힙
graph: 입력으로 주어지는 그래프를 저장 [다음 노드, 다음 가중치]

"""

INF = sys.maxsize
V, E = map(int,input().split())
K = int(input())
graph = [[] for i in range(V+1)]
dp = [INF] * (V+1)
heap = []

#경로
for i in range(E):
    u, v, w = map(int,input().split())
    graph[u].append((v,w))

def dijkstra(start):
    dp[start] = 0
    heapq.heappush(heap, (start, 0))

    while heap:
        cur_node, cur_w = heapq.heappop(heap)

        #최단거리가 아니면 넘어감
        if dp[cur_node] < cur_w:
            continue

        for next_node, w in graph[cur_node]:
            next_w = cur_w + w

            #더 짧은 거리라면, 새로 바꾸고 heap에 추가
            if next_w < dp[next_node]:
                dp[next_node] = next_w
                heapq.heappush(heap, (next_node, next_w))

dijkstra(K)
for i in dp[1:]:
    print(i if i != INF else "INF")

 

 

 

 

 

맞힌 코드

import heapq
import sys
input = sys.stdin.readline

"""
다익스트라 알고리즘

-변수-
dp: 최종 비용을 저장해둠
heap: 가중치를 계산하기위해 사용하는 힙
graph: 입력으로 주어지는 그래프를 저장 [다음 노드, 다음 가중치]

"""

INF = sys.maxsize
V, E = map(int,input().split())
K = int(input())
graph = [[] for i in range(V+1)]
dp = [INF] * (V+1)
heap = []

#경로
for i in range(E):
    u, v, w = map(int,input().split())
    graph[u].append((w, v))

def dijkstra(start):
    dp[start] = 0
    heapq.heappush(heap, (0, start))

    while heap:
        cur_w, cur_node = heapq.heappop(heap)

        #최단거리가 아니면 넘어감
        if dp[cur_node] < cur_w:
            continue

        for w, next_node in graph[cur_node]:
            next_w = cur_w + w

            #더 짧은 거리라면, 새로 바꾸고 heap에 추가
            if next_w < dp[next_node]:
                dp[next_node] = next_w
                heapq.heappush(heap, (next_w, next_node))

dijkstra(K)
for i in dp[1:]:
    print(i if i != INF else "INF")

68376

708