[백준1504] / 특정한 최단 경로 - 다익스트라

 

백준1504

 

 

푼 날짜 : 2024.11.11

푼 문제 : [1504] / 특정한 최단 경로

사용한 언어 : python

알고리즘 : 다익스트라(dijkstra)

 

 

접근 방식 :

주어진 두 정점을 반드시 거쳐야 하므로 

• 1 -> v1 -> v2 -> N
• 1 -> v2 -> v1 -> N

이렇게 두 경로를 계산해서 작은 값으로 출력했다.

 

따라서 

• 1 -> v1 -> v2 -> N

를 구하려면 (1 -> v1) + (v1 -> v2) + (v2-> N) 이렇게 경로에 대한 값을 각각 구해서 더해주었다.

 

 

 

코드 : 

import sys
import heapq

N, M = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(N+1)]
for _ in range(M):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a].append((b, c))
    graph[b].append((a, c))

v1, v2 = map(int, sys.stdin.readline().split())

def dijkstra(start, end):

    heap = [(start, 0)]
    dist = [float("INF") for _ in range(N+1)]
    dist[start] = 0

    while heap:
        n_node, n_cost = heapq.heappop(heap)

        if dist[n_node] < n_cost: continue

        for  node, cost in graph[n_node]:
            all_cost = n_cost + cost

            if dist[node] > all_cost:
                dist[node] = all_cost
                heapq.heappush(heap, (node, all_cost))
                
    return dist[end]

# 1 -> v1 -> v2 -> N
ans = dijkstra(1, v1) + dijkstra(v1, v2) + dijkstra(v2, N)
# 1-> v2 -> v1 -> N
ans2 = dijkstra(1, v2) + dijkstra(v2, v1) + dijkstra(v1, N)

# 작은 값으로 출력
print(min(ans, ans2) if min(ans, ans2) < float("INF") else -1)

 

 

 

헤헤 heappush에서 all_cost를 넣어주어야 하는걸 자꾸 cost를 넣어줘서 틀렸었다.

앞으로는 실수하지 않도록 조심해야지~