[프로그래머스] 합승 택시 요금

신기하게도 백준에서 플로이드-와샬 문제를 딱 풀고 왔는데 이 문제더라구요.. 근데 여전히 플로이드 와샬이라는 것을 떠올리는 것이 조금 어려웠습니다.

일단 답을 구하기 위해 필요한 것은 출발점부터 각 지점에 이르는 최소 비용 그리고 각 지점으로부터 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