[백준] 1504 파이썬(python) : 특정한 최단 경로 - 다익스트라

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

1504번: 특정한 최단 경로

 

 

특정노드를 반드시 지나서 가야하는 다익스트라 알고리즘 문제이다. 이전 문제(1916)에서 조건이 추가된 문제.

https://hgk5722.tistory.com/179

[백준] 1916 파이썬(python) : 최소비용 구하기 - 다익스트라

 

import heapq
import sys
n, e = map(int, sys.stdin.readline().split())
graph = [ [] for _ in range(n+1) ]
for _ in range(e):
    x, y, cost = map(int, sys.stdin.readline().split())
    graph[x].append((cost, y))
    graph[y].append((cost, x))
stop1, stop2 = map(int, sys.stdin.readline().split())
INF = int(1e9)

def djikstra(start, end):
    visit = [INF]*(n+1) #1
    visit[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    while q:
        cost, x = heapq.heappop(q)
        if visit[x] < cost:
            continue
        for new_cost, new_node in graph[x]:
            nc = new_cost + visit[x]
            if visit[new_node] > nc:
                visit[new_node] = nc
                heapq.heappush(q, (nc, new_node))
    return visit[end]
path1 = djikstra(1, stop1) + djikstra(stop1, stop2) + djikstra(stop2, n) #2
path2 = djikstra(1, stop2) + djikstra(stop2, stop1) + djikstra(stop1, n) 

if path1 >= INF and path2 >= INF: #3
    print(-1)
else:
    print(min(path1, path2))

 

#1 : 여러번 최단거리를 찾아줘야 하기에 visit 초기화

#2 : path1과 path2를 구하는 방법

#3 : 최단거리를 찾을 수 없어서 갱신을 하지 못한 경우

 

path1 = 1 -> stop1 -> stop2 -> 도착노드(n번노드)

path2 = 1 -> stop2 -> stop1 -> 도착노드(n번노드)

 

다익스트라 알고리즘은 bfs, dfs랑 조금 다른것 같다.