1504_특정한 최단경로

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

1504번: 특정한 최단 경로

 

다익스트라 알고리즘을 통해 저번에 최단경로를 구했었는데 이를 활용해서 풀었다.

 

결국 v1,v2 두개의 점을 통과하여 통과하려면

 

1 -> v1 -> v2 -> N

1 -> v2 -> v1 -> N

 

두가지 방법이 존재한다.

 

즉, 1,v1,v2 에서 다른 점들로의 최단거리를 구해놓은 배열을 하나 만들고, 위 방법에 따라서 최단거리를 정해주면 된다.

 

import sys
import heapq
input = sys.stdin.readline

n,e = map(int,input().split())
INF = int(1e9)
graph = [ [] for _ in range(n+1)]
distance = [ [INF] * (n+1) for _ in range(n+1) ]
for _ in range(e):
    a,b,c = map(int,input().split())
    graph[a].append([b,c])
    graph[b].append([a,c])

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


for i in [1,v1,v2]:

    q = []
    heapq.heappush(q,[0,i])
    distance[i][i] = 0

    while q:
        cnt,node = heapq.heappop(q)
        if distance[i][node] < cnt:
            continue
        for j,k in graph[node]:
            if cnt + k < distance[i][j]:
                distance[i][j] = cnt + k
                heapq.heappush(q,[cnt+k,j])


result = min(distance[1][v1]+distance[v1][v2]+distance[v2][n],distance[1][v2]+distance[v2][v1]+distance[v1][n])
print(result if result < INF else -1)

 

 

어떻게보면 한점에서 다른점으로 가는 최단거리를 구했던 저번문제의 응용이라고 봐도 될 것 같다.