특정한 정점을 반드시 거쳐야하는 최단 경로를 구하는 다익스트라 응용

1. 문제

 

 

1504번: 특정한 최단 경로 (acmicpc.net)

1504번: 특정한 최단 경로

 

 

1번부터 n번까지 최단 경로로 이동하고 싶은데, 특정한 정점 v1,v2를 반드시 거쳐서 최단 경로로 가고 싶다면 어떻게 해야할까?

 

 

2. 풀이

 

다익스트라는 어떤 정점에서 나머지 정점까지 도달하는 최단 경로를 제공하는데, 여기 중간에 어떤 정점을 거칠지는 말해주지 않는다...

 

근데 어떤 정점을 반드시 거쳐가게 할려면 어떻게 해야할까?

 

생각보다 간단하다

 

1번부터 v1번까지 최단 경로로 가고, v1번에서 v2번까지 최단 경로로 가고, v2번에서 n번까지 최단경로로 간다면

 

1번에서 n번까지 최단 경로로 가는 것이다

 

그러면 1번부터 v1번까지 최단 경로로 가는건 어떻게 구해?

 

1번을 start로 하는 다익스트라 알고리즘으로 distance 배열을 구해놓으면, 1번에서 v1번까지 가는 최단 거리를 알 수 있다

 

v1번에서 v2번까지 최단 경로는? v1번을 start로 하는 다익스트라로 distance 배열을 구하면 된다

 

v2번에서 n번까지 최단경로는? v2번을 start로 하는 다익스트라로 distance 배열을 구하면 된다

 

그런데 1번에서 n번까지가 이런 경우만 있나???

 

1 > v2 > v1 > n으로도 가능하다

 

import heapq
from sys import stdin

def dijkstra(start,distance):
    
    q = []

    heapq.heappush(q,(0,start))

    distance[start] = 0

    while q:
        
        dist,u = heapq.heappop(q)

        if distance[u] < dist:
            
            continue
        
        for b,c in graph[u]:
            
            cost = dist + c

            if cost < distance[b]:
                
                distance[b] = cost

                heapq.heappush(q,(cost,b))
    
    return distance

n,e = map(int,stdin.readline().split())

graph = [[] for _ in range(n+1)]

for _ in range(e):
    
    a,b,c = map(int,stdin.readline().split())

    graph[a].append((b,c))
    graph[b].append((a,c))

INF = 100000000000000000

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

##1,v1,v2를 start로 하는 다익스트라를 3번 적용해서 distance배열 3개를 구함

distance1 = dijkstra(1,[INF]*(n+1))

distance2 = dijkstra(v1,[INF]*(n+1))

distance3 = dijkstra(v2,[INF]*(n+1))

a = distance1[v1]+distance2[v2]+distance3[n] #1>v1>v2>n
b = distance1[v2]+distance3[v1]+distance2[n] #1>v2>v1>n

ans = min(a,b)

if ans >= INF: ##도달할 수 없는 경우는 INF 이상이 되는 경우
    
    print(-1)

else:
    
    print(ans)

 

그리고 문제에서 도달할 수 없으면 -1을 출력하라고 하더라..

 

도달할 수 없는 경우는 distance 배열에서 INF로 되는데

 

a = distance1[v1]+distance2[v2]+distance3[n] 
b = distance1[v2]+distance3[v1]+distance2[n] 

 

근데 a,b가 정확히 INF가 되는것보다 3개의 항이 모두 INF가 될수도 있겠지?? 그런 경우에 최솟값은 INF 이상이 되는 경우 -1을 출력하도록 하는게 맞겠지?