1. 문제 설명

합승 택시 요금

2. 문제 분석

플로이드-워셜 알고리즘을 통해 모든 노드에서 다른 모든 노드에 대한 최단 거리를 찾는다. 이를 통해 s에서 a, b를 들를 때 도착하는 최솟값을 알 수 있다. 즉 출발지인 s는 고정, x까지 함께 갔을 때 a, b에 도착하는 값을 합했을 때 최소인지 구할 수 있는 것이다.

3. 나의 풀이

import Foundation

func solution(_ n:Int, _ s:Int, _ a:Int, _ b:Int, _ fares:[[Int]]) -> Int {
    let INF = Int.max
    var nodes = Array(repeating: Array(repeating: INF, count: n+1), count: n+1)
    for i in 0..<n+1 {
        nodes[i][i] = 0
    }
    for fare in fares {
        let (c, d, f) = (fare[0], fare[1], fare[2])
        nodes[c][d] = f
        nodes[d][c] = f
    }
    for k in 1..<n+1 {
        for i in 1..<n+1 {
            for j in 1..<n+1 {
                if nodes[i][k] == INF || nodes[k][j] == INF {
                    continue
                }
                
                if nodes[i][j] > nodes[i][k] + nodes[k][j] {
                    nodes[i][j] = nodes[i][k] + nodes[k][j]
                }
            }
        }
    }
    var total = INF
    
    for i in 1..<n+1 {
        if nodes[s][i] == INF || nodes[i][a] == INF || nodes[i][b] == INF {
            continue
        }
        let route = nodes[s][i] + nodes[i][a] + nodes[i][b]
        total = min(total, route)
    }
    return total
}