import heapq
def solution(n, s, a, b, fares):
answer = float('inf')
total_node = set(range(1,n+1))
graph = [{} for i in range(n+1)]
for start,end,fee in fares:
graph[start][end] = fee
graph[end][start] = fee
def distra(start,end):
nonlocal graph,n
node_list = []
heapq.heappush(node_list,(0,start))
INF = float('inf')
Fee_list = [INF]*(n+1)
Fee_list[start] = 0
while node_list:
fee,node = heapq.heappop(node_list)
if fee > Fee_list[node]:
continue
if node == end:
return fee
for next_node in graph[node]:
temp_fee = fee + graph[node][next_node]
if Fee_list[next_node]> temp_fee:
Fee_list[next_node] = temp_fee
heapq.heappush(node_list,(temp_fee,next_node))
return INF
for k in total_node:
answer = min(answer,distra(s,k)+distra(k,a)+distra(k,b))
return answer
solution(7,3,4,1,[[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]])
처음엔 다익스트라로 만들어서 풀었다. 이 풀이의 문제점은 한번했던 다익스트라를 계속하기 때문에, 시간이 오래걸리는 문제가 있었다.
import heapq
def solution(n, s, a, b, fares):
answer = float('inf')
INF = float('inf')
graph = [[INF if x!=y else 0 for x in range(n+1)] for y in range(n+1)]
for start,end,fee in fares:
graph[start][end] = fee
graph[end][start] = fee
for mid in range(1,n+1):
for start in range(1,n+1):
for end in range(1,n+1):
if graph[start][end] > graph[start][mid] + graph[mid][end]:
graph[start][end] = graph[start][mid] + graph[mid][end]
for k in range(1,n+1):
answer = min(answer,graph[s][k]+graph[k][a]+graph[k][b])
return answer
위의 문제가 매번 다읷트라를 계산하는것을 벗어나기 위해 플로이드 와샬로 각 노드에서 다른노드까지의 최저비용을 갱신해놓고, 그 합의 최저값을 구하는 방식으로 했다.
import heapq
def solution(n, s, a, b, fares):
answer = float('inf')
INF = float('inf')
graph = [{} for i in range(n+1)]
for start,end,fee in fares:
graph[start][end] = fee
graph[end][start] = fee
Fee_list = [[INF]*(n+1) for _ in range(3)]
def distra(start,idx):
nonlocal graph,n,Fee_list
node_list = []
heapq.heappush(node_list,(0,start))
Fee_list[idx][start] = 0
while node_list:
fee,node = heapq.heappop(node_list)
if fee > Fee_list[idx][node]:
continue
for next_node in graph[node]:
temp_fee = fee + graph[node][next_node]
if Fee_list[idx][next_node]> temp_fee:
Fee_list[idx][next_node] = temp_fee
heapq.heappush(node_list,(temp_fee,next_node))
distra(s,0)
distra(a,1)
distra(b,2)
for mid in range(1,n+1):
temp = Fee_list[0][mid] + Fee_list[1][mid] + Fee_list[2][mid]
if answer > temp:
answer = temp
return answer
solution(7,3,4,1,[[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]])
마지막은 www.youtube.com/watch?v=FX9n1PFv2K4 유튜브의 barkingdog님의 풀이를 참조해서 푼 방식이다.
제일 첫번째의 매번 다익스트라를 하던것을 총 3번의 다익스트라로 그 값들을 전부 저장해놓고 푸는 방식이다.
자세한 설명은 유튜브를 참조하길 바란다.