https://www.acmicpc.net/problem/1504
1번 정점에서 n번 정점으로 이동할 때, 임의로 주어진 두 정점을 반드시 통과해서 지나야 한다.
1번 정점에서 n번 정점으로 이동할 때, 거쳐야 하는 두 정점 v1, v2의 경우를 따로 비교해야 한다.
이 문제를 풀려면 이 생각을 먼저 떠올려야 하는 것 같다. 💭
[1] 1번 ➣ v1 ➣ v2 ➣ n번
1번이 출발지이고, v1이 도착지일때 가장 짧은 경로
+v1이 출발지이고, v2가 도착지일때 가장 짧은 경로
+v2가 출발지이고, n번이 도착지일때 가장 짧은 경로
[2] 1번 ➣ v2 ➣ v1 ➣ n번
1번이 출발지이고, v2가 도착지일때 가장 짧은 경로
+v2가 출발지이고, v1이 도착지일때 가장 짧은 경로
+v1이 출발지이고, n번이 도착지일때 가장 짧은 경로
두 정점을 거칠 때, 위와 같은 경우로 나누어서 더 짧은 경로를 선택해서 출력해주면 된다.
answer
변수에 저장하기answer
가 MAX_INT
값보다 크면 이동할 수 없는 경로이므로 -1
을 리턴해준다.import sys
import heapq
input = sys.stdin.readline
MAX_INT = sys.maxsize
def dijkstra(start):
distance = [MAX_INT for _ in range(n+1)]
q = [start] # [비용,시작점]
# 자기 자신의 거리 0으로 만들기
distance[start[1]] = 0
while q:
p = heapq.heappop(q)
cur_cost, cur_location = p[0], p[1]
# 현재 위치한 정점과 연결된 정점 Next 들 방문
for next_cost, next_location in graph[cur_location]:
# (연결된 정점으로 이동 비용) vs (현재 비용 + 이동 비용): 더 작은 값으로 할당 해줌
if distance[next_location] > cur_cost + next_cost:
distance[next_location] = cur_cost + next_cost
heapq.heappush(q,[distance[next_location],next_location])
return distance
n,e = map(int,input().rstrip().rsplit())
graph = [[] for _ in range(n+1)]
for _ in range(e):
a, b, c = map(int,input().rstrip().rsplit())
# graph[출발지] = [비용,도착지]
graph[a].append([c,b])
graph[b].append([c,a])
# 경유지 v1, v2
v1, v2 = map(int,input().rstrip().rsplit())
go = dijkstra([0,1])
v1go = dijkstra([0,v1])
v2go = dijkstra([0,v2])
answer = (min(go[v1]+v1go[v2]+v2go[n],go[v2]+v2go[v1]+v1go[n]))
if answer >= MAX_INT:
print(-1)
else:
print(answer)