[2021 KAKAO BLIND RECRUITMENT Level 3] 합승 택시 요금

function solution(n, s, a, b, fares) {
    const costs = Array.from({ length: n + 1 }, () => new Array(n + 1).fill(Infinity));
 
    // 지점 사이의 예상 택시요금 업데이트
    fares.forEach(([dep, arr, fare]) => costs[dep][arr] = costs[arr][dep] = fare);
 
    function dijkstra(start){
        // 지점별 요금
        const dist = [...costs[start]];
        const visited = new Array(n + 1).fill(false);
 
        function getShortestIdx(){
            let min = Infinity;
            let idx = 0;
 
            dist.forEach((v, i) => {
                if(v < min && !visited[i]){
                    min = v;
                    idx = i;
                }
            });
 
            return idx;
        }
 
        // 출발지 초기화
        dist[start] = 0;
        visited[start] = true;
 
        for(let i = 1; i <= n - 2; i++){
            const current = getShortestIdx();
 
            visited[current] = true;
 
            for(let j = 1; j <= n; j++){
                if (visited[j]) continue;
 
                if (dist[current] + costs[current][j] < dist[j]){
                    dist[j] = dist[current] + costs[current][j];
                }
            }
        }
 
        return dist;
    }
 
    const from_s = dijkstra(s);
    const from_a = dijkstra(a);
    const from_b = dijkstra(b);
 
    let min = Infinity;
 
    for (let i = 1; i <= n; i++) {
        min = Math.min(min, from_s[i] + from_a[i] + from_b[i]);
    }
 
    return min;
}