[프로그래머스 Level 2] 배달

function solution(N, road, K) {
    const map = Array.from({ length: N }, () => new Array(N).fill(Infinity));
 
    road.forEach(([v1, v2, takes]) => {
        v1-- && v2--;
        map[v1][v2] = map[v2][v1] = Math.min(map[v1][v2], takes);
    });
 
    function dijkstra(source){
        const dist = [...map[source]];  // ✅ 우선순위 큐로 개선 가능
        const visited = new Array(N).fill(false);
 
        // O(N)
        function getSmallIdx(){
            let min = Infinity;
            let idx = 0;
 
            // 1 ≤ N ≤ 50
            dist.forEach((v, i) => {
                if(v < min && !visited[i]){
                    min = v;
                    idx = i;
                }
            });
 
            return idx;
        }
 
        dist[source] = 0;
        visited[source] = true;
 
        // O(N^2) → (N-2) * (N + N)
        for(let i = 0; i < N - 2; i++){
            const current = getSmallIdx();
 
            visited[current] = true;
 
            for(let j = 0; j < N; j++){
                if(visited[j]) continue;
                if(map[current][j] === Infinity) continue;
 
                dist[j] = Math.min(dist[j], dist[current] + map[current][j]);
            }
        }
 
        return dist;
    }
 
    return dijkstra(0).filter(v => v <= K).length;
}