📩 출처
문제
서준이는 아빠로부터 생일선물로 세계 지도를 받아서 매우 기뻤다. 세계 지도에서 최단 경로를 찾는 프로그램을 개발해서 아빠께 감사의 마음을 전달하려고 한다. 세계 지도는 도시를 정점으로 갖고 도시 간의 도로를 간선으로 갖는 방향성 그래프이며(directed graph), 도로의 길이가 간선의 가중치이다. 도시의 번호는 1부터 N까지이다. 출발 정점 X에서 출발하여 중간 정점 Y를 거쳐서 도착 정점 Z에 도달하는 최단 거리, 출발 정점 X에서 출발하여 중간 정점 Y를 거치지 않고 도착 정점 Z에 도달하는 최단 거리를 각각 구해서 우리 서준이를 도와주자.
입력
첫째 줄에 정점의 수 N (1 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000)이 주어진다.
다음 M개 줄에 간선 정보 u v w가 주어지며 도시 u에서 도시 v로 가중치가 w인 단방향 도로를 나타낸다. (1 ≤ u, v ≤ N, u ≠ v, 1 ≤ w ≤ 10,000, w는 정수) 모든 간선의 (u, v) 쌍의 값은 서로 다르다.
다음 줄에 X Y Z가 주어진다. (1 ≤ X, Y, Z ≤ N, X ≠ Y, X ≠ Z, Y ≠ Z)
출력
첫째 줄에 두 정수를 출력한다. 첫 번째 정수는 정점 X에서 출발해서 정점 Y를 거쳐서 정점 Z에 도달하는 최단 거리를 의미한다. 두 번째 정수는 정점 X에서 출발해서 정점 Y를 거치지 않고 정점 Z에 도달하는 최단 거리를 의미한다.
만약, 정점 Z에 도달할 수 없는 경우 -1을 출력한다.
👉 생각
- x에서 y를 거쳐 z로 가는 최단 경로는 그냥 x에서 y로 다익스트라로 최단 경로를 구하고 y에서 z로 다익스트라를 구해서 더해주면 된다.
- y를 거치지 않는 방법은 우선 순위 큐에서 나온 정점이 y로 간다면 가지 않고 그 다음으로 넘어가면 된다!
import sys, heapq
def dijkstra(start, end, is_check):
heap = []
heapq.heappush(heap, [0, start])
d = [INF] * (n+1)
d[start] = 0
if is_check:
while heap:
check, i = heapq.heappop(heap)
if d[i] < check:
continue
for v, w in adj[i]:
tmp = check + w
if d[v] > tmp:
d[v] = tmp
heapq.heappush(heap, [tmp, v])
else:
while heap:
check, i = heapq.heappop(heap)
if d[i] < check:
continue
for v, w in adj[i]:
if v == y:
continue
tmp = check + w
if d[v] > tmp:
d[v] = tmp
heapq.heappush(heap, [tmp, v])
return d
n, m = map(int, input().split())
adj = [[] for _ in range(n+1)]
INF = sys.maxsize
for _ in range(m):
u, v, w = map(int, sys.stdin.readline().split())
adj[u].append((v, w))
x, y, z = map(int, input().split())
res = dijkstra(x, y, True)[y] + dijkstra(y, z, True)[z]
res = res if res < INF else -1
print(res, end = ' ')
ans = dijkstra(x, z, False)[z]
print(ans if ans < INF else -1)