[다익스트라 알고리즘] 특정한 최단 경로

기출 : 백준 #1504

 

1 -> v1 -> v2 -> n

1 -> v2 -> v1 -> n

 

위의 두 가지 경로를 고려하여 최솟값을 출력하면 된다

 

from heapq import heappop, heappush
INF = int(1e9)

n, e = map(int,input().split())
graph = [[]for _ in range(n+1)]
queue = list()

for _ in range(e):
    x,y,w = map(int,input().split())
    graph[x].append((w, y))
    graph[y].append((w, x))

v1, v2 = map(int,input().split())

def dijkstra(start, end):
    distance = [INF for _ in range(n+1)]
    distance[start] = 0
    heappush(queue, (0, start))
    while queue:
        curVal, cur = heappop(queue)
        if distance[cur] < curVal:
            continue
        for nextVal, next in graph[cur]:
            if distance[next] > curVal + nextVal:
                distance[next] = curVal + nextVal
                heappush(queue, (curVal + nextVal, next))
    return distance[end]

way1 = dijkstra(1,v1) + dijkstra(v1,v2) + dijkstra(v2, n)
way2 = dijkstra(1,v2) + dijkstra(v2,v1) + dijkstra(v1, n)
minWay = min(way1, way2)
if minWay>=INF:
    print(-1)
else:
    print(minWay)