[최단거리] 합승택시요금

문제

플루이드 워셜 알고리즘을 응용하면 되는 문제였다.

플루이드 워셜 알고리즘은 O(n^3) 복잡도를 가지기 때문에 노드의 개수가 많으면 안된다. 하지만 문제에서 노드는 200개 이하이기때문에 가능했다.

핵심 아이디어는
플루이드 워셜로 최소비용테이블을 완성해놓고 각 노드마다 해당 노드를 중간기점으로 해서 a, b를 가는 비용의 합을 계산(비용테이블에서 a,b,시작점의 비용의 총합)
합승을 안하는 경우를 생각해서 s에서 a, b 각각 최소 비용 합보다 위의 합이 적을때 합승하도록함.

def solution(n, s1, a1, b1, fares):
    INF = int(1e9)
    graph = [[INF for _ in range(n+1)] for _ in range(n+1)]

    for a in range(1, n+1):
        for b in range(1, n+1):
            if a==b:
                graph[a][b] = 0

    for f in fares:
        a, b, c = f
        # 양방향 모두 비용 추가
        graph[a][b] = c 
        graph[b][a] = c
        
	# 플루이드-워셜 알고리즘
    for k in range(1, n+1):
        for a in range(1, n+1):
            for b in range(1, n + 1):
                graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
	
    # 최소비용 계산
    small = INF
    for i in range(1, n+1):
        if small > (graph[i][a1] + graph[i][b1] + graph[i][s1]):
            small = graph[i][a1] + graph[i][b1] + graph[i][s1]
     
     # 합승안하는 경우까지 생각     
    if small > graph[s1][a1] + graph[s1][b1]:
        return graph[s1][a1] + graph[s1][b1]
     
    return small

느낀점
문제를 처음봤을때는 되게 어려워보였는데 다익스트라, 플루이드워셜 원리를 공부할때 배운 시작노드나 도착노드를 기준으로 생각하는 것이 아닌 거쳐가는 중간 노드를 기준으로 생각하니까 아이디어가 나왔다.
쫄지말장!!