배달

https://programmers.co.kr/learn/courses/30/lessons/12978

코딩테스트 연습 - 배달

다익스트라 사용

function solution(N, road, K) {
    const r = Array.from(new Array(N + 1), () => []);
    const cost = new Array(N + 1).fill(Infinity);
    const pq = [];
    road.forEach(([from, to, w]) => {
        r[from].push({to, w});
        r[to].push({to: from, w});
    });
    cost[1] = 0;
    pq.push({to: 1, w: 0});
    
    while (pq.length) {
        pq.sort((a, b) => a.w - b.w);
        const { to, w } = pq.pop();
        
        for (let i = 0; i < r[to].length; i++) {
            const next = r[to][i];
            if (cost[next.to] > cost[to] + next.w) {
                cost[next.to] = cost[to] + next.w;
                pq.push(next);
            }
        }
    }
    return cost.filter((v) => v <= K).length;
}