[TIL] 2023-09-16 코테 (그래프)

Lv 3. 합승 택시 요금

풀이

그래프 내에서 최단 거리를 구해야한단거는 캐치했는데 최종 로직이 안 나와서 해설을 참고했다. 이 문제는 특정 지점까지 합승을 하고, 그 뒤는 따로 이동하는 경우다.

따라서 최단거리는 k번 노드까지 합승을 하고, k번 노드에서 각자 따로 가는 경우를 1~n번까지 돌면서 최솟값을 구해줘야한다.

코드

# 최종 로직이 안떠올라 해설 참고
def floyd(graph, n):
    for k in range(1, n+1):
        for a in range(1, n+1):
            for b in range(1, n+1):
                if graph[a][b] > graph[a][k] + graph[k][b]:
                    graph[a][b] = graph[a][k] + graph[k][b]
    return graph

def solution(n, s, a, b, fares):
    graph = [[int(1e9) for _ in range(n+1)] for _ in range(n+1)]
    
    for c, d, f in fares:
        graph[c][d] = f
        graph[d][c] = f
    
    for i in range(1, n+1):
        graph[i][i] = 0
        
    graph = floyd(graph, n)
    
    answer = int(1e9)
    # k까지 합승한다고 고려, s->k + k->a + k->b (이걸 떠올려야함)
    for k in range(1, n+1):
        answer = min(answer, graph[s][k] + graph[k][a] + graph[k][b])
    
    return answer