노드 별 최단 거리를 구해
특정 구간 c
를 경유해a
,b
에 도착한 경로별 거리를 구하자.
경유
한 거리보다 길다면, 곧바로 직진하는 것보다 k번 노드를 경유해야 한다. 즉, if nodes[i][j] > nodes[i][k] + nodes[k][j] then update or keep
s ▷ c
, c ▷ a
, c ▷ b
를 통해 세 노드를 모두 거치면서 그 합이 최소인 방법을 찾자. 즉 어떤 노드까지 a
, b
가 같이 갔을 때 최단 거리인지 구해야 한다.def solution(n, s, a, b, fares):
INF = 100001*n
# 요금 최댓값 100000
nodes = [[INF for _ in range(n+1)] for _ in range(n+1)]
for tail, head, cost in fares:
nodes[tail][head] = cost
nodes[head][tail] = cost
for i in range(n+1):
for j in range(n+1):
if i == j: nodes[i][j] = 0
# 플로이드-워셜 알고리즘 사용 -> 모든 노드에 대한 각 노드의 최단 거리
for k in range(n+1):
for i in range(n+1):
for j in range(n+1):
if nodes[i][j] > nodes[i][k] + nodes[k][j]:
nodes[i][j] = nodes[i][k] + nodes[k][j]
upto_c = [0]*(n+1)
# s -> i, i -> a + i -> b 최단 거리, 'i'번 노드까지 동승 후 따로 간다.
for i in range(n+1):
upto_c[i] = nodes[s][i] + nodes[i][a] + nodes[i][b]