[알고리즘] 특정한 최단 경로 1504 python

문제 바로가기

---

풀이

최단경로 문제는 Dijkstra 알고리즘을 사용하는 경우가 많습니다.
요 문제를 풀기 전에 근본 문제 요것을 먼저 풀어보시는 것을 추천드립니다.
Dijkstra 알고리즘의 자세한 설명도 위 링크에 있슴니다!!!!!!

기본적인 최단거리 문제에서 반드시 지나야하는 두 개의 노드라는 제약 사항이 추가됐습니다.

두 개의 노드를 반드시 지나는 경로는
1. 1번 노드에서 must1까지의 최단 경로 + must1~must2 최단 경로 + must2~마지막 노드 최단경로
2. 1번 노드에서 must2까지의 최단 경로 + must2~must1 최단 경로 + must1~마지막 노드 최단경로
중 작은 것을 선택하면 된다!

끝~

import sys
import heapq

def dijkstra(start):
    pq = []
    heapq.heappush(pq, (0, start))
    dist = [INF] * (node_count + 1)
    dist[start] = 0
    while(pq):
        curDist, curNode = heapq.heappop(pq)
        if dist[curNode] < curDist:
            continue
        for destNode, destDist in graph[curNode]:
            d = curDist + destDist
            if dist[destNode] > d:
                dist[destNode] = d
                heapq.heappush(pq, (d, destNode))
    return dist

INF = sys.maxsize
node_count, line_count = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(node_count+1)]

for _ in range(line_count):
    start, dest, weight = map(int, sys.stdin.readline().split())
    graph[start].append((dest, weight))
    graph[dest].append((start, weight))
    
must1, must2 = map(int, sys.stdin.readline().split())

start_dist = dijkstra(1)
must1_dist = dijkstra(must1)
must2_dist = dijkstra(must2)

path1 = start_dist[must1] + must1_dist[must2] + must2_dist[node_count]
path2 = start_dist[must2] + must2_dist[must1] + must1_dist[node_count]

result = min(path1, path2)

if result >= INF:
    print(-1)
else:
    print(result)