Koala - 4기
[프로그래머스] 합승 택시 요금
beans3142
2021. 8. 12. 18:08
신기하게도 백준에서 플로이드-와샬 문제를 딱 풀고 왔는데 이 문제더라구요.. 근데 여전히 플로이드 와샬이라는 것을 떠올리는 것이 조금 어려웠습니다.
일단 답을 구하기 위해 필요한 것은 출발점부터 각 지점에 이르는 최소 비용 그리고 각 지점으로부터 a,b까지 드는 비용이라고 생각했습니다. 이것을 확신하고 이해하는게 첫 번째 어려움이였고, 이 3가지 값의 합 중 가장 작은 값이 정답이라는 생각은 첫 번째 어려움을 거치니 별로 어렵지 않게 해냈습니다.
from sys import maxsize
def solution(n,s,a,b,fares):
inf = maxsize
mn=inf
value_table=[[inf for i in range(n)]for _ in range(n)]
for start,end,cost in fares:
value_table[start-1][end-1]=cost
value_table[end-1][start-1]=cost
for i in range(n):
value_table[i][i]=0
for j in range(n):
for k in range(n):
value_table[j][k]=min(value_table[j][k],value_table[j][i]+value_table[i][k])
for dest,start_cost in enumerate(value_table[s-1]):
if start_cost!=inf:
mn=min(mn,start_cost+value_table[dest][a-1]+value_table[dest][b-1])
return mn