1800 인터넷 설치 (자바스크립트)

문제

오늘 팀전을 다들 열심히 하시는 것을 보고 원장선생님은 세미나 실에 인터넷을 설치해 주기로 마음을 먹으셨다. 하지만 비 협조적인 코레스코 콘도는 원장님께서 학생들에게 인터넷 선을 연결하는 것에 대해서 일부에 대해 돈을 요구하였다.

각각의 학생들의 번호가 1부터 N까지 붙여져 있다고 하면 아무나 서로 인터넷 선이 연결되어 있지 않다. P(P<=10,000)개의 쌍만이 서로 이어 질수 있으며 서로 선을 연결하는데 가격이 다르다.

1번은 다행히 인터넷 서버와 바로 연결되어 있어 인터넷이 가능하다. 우리의 목표는 N번 컴퓨터가 인터넷에 연결하는 것이다. 나머지 컴퓨터는 연결 되어 있거나 연결 안되어 있어도 무방하다.

하지만 코레스코에서는 K개의 인터넷 선에 대해서는 공짜로 연결해주기로 하였다. 그리고 나머지 인터넷 선에 대해서는 남은 것 중 제일 가격이 비싼 것에 대해서만 가격을 받기로 하였다. 이때 원장선생님이 내게 되는 최소의 값을 구하여라.

입력

첫 번째 줄에 N(1 ≤ N ≤ 1,000), 케이블선의 개수 P(1 ≤ P ≤ 10,000), 공짜로 제공하는 케이블선의 개수 K(0 ≤ K < N)이 주어진다. 다음 P개의 줄에는 케이블이 연결하는 두 컴퓨터 번호와 그 가격이 차례로 들어온다. 가격은 1 이상 1,000,000 이하다.

출력

첫째 줄에 원장선생님이 내게 되는 최소의 돈을 출력한다. 만약 1번과 N번 컴퓨터를 잇는 것이 불가능 하다면 -1을 출력한다.

====

문제 분석

문제를 처음 풀려고 했던 방식은 최소힙에 [최대 돈, 현재 노드, 최대 k길이를 가지는 배열] 을 담은 뒤 최대 돈을 우선순위로 뽑아가면서 배열이 k길이보다 작다면 [0,다음노드,[...src, 다음 노드까지의 가중치 돈 ] ] 을 넣어서 처리했다. 이 때 가중치 돈을 담은 배열은 이진 검색으로 적절한 위치에 삽입하여 오름 차순 정렬한담에 k길이가 된다면 가중치 돈을 넣고 제일 작은 값을 꺼내어 최대 돈과 방금 꺼낸 걸 비교하여 더 큰 것을 기준으로 힙큐에 다시 넣는...  (이렇게 할 경우 방문 처리를 하는 것이 힘들었다.)

위 방법 대신 기준이 되는 돈을 정한 뒤에 이것보다 크면 무료 설치 처리 하고 아니라면 더 큰 값을 힙큐에 넣는 방식을 사용했다.

만약 기준 값을 만족하면서 탐색이 됐다면, 기준 값을 더 낮춰주고 안된다면 기준 값을 올려주는 이진 검색 방식 사용.

 

방문 노드는 [노드 갯수][k 갯수] 로 선언하여 다음의 가중치가 기준 값보다 크다면 count를 +1 하여 무료 처리를 할건데 count가 이미 k만큼 사용했다면 패스, 또한 이미 [다음 노드] [사용한 k갯수] 보다 최댓값이 크다면 패스 하는 방식으로 탐색 후 이 기준 돈을 만족했다면 end= pivot-1 만족 못했다면 start=pivot+1로 범위를 줄이거나 늘리기 시도.

class Heap {
    heapq;
    constructor() {
        this.heapq = [undefined];
    }
    isEmpty() {
        return this.heapq.length === 1;
    }
    swap(src, des) {
        [this.heapq[src], this.heapq[des]] = [this.heapq[des], this.heapq[src]];
    }
    push(arr) {
        this.heapq.push(arr);
        let cur = this.heapq.length - 1;
        while (cur > 1) {
            let parent = Math.floor(cur / 2);
            if (this.heapq[parent][0] > this.heapq[cur][0]) {
                this.swap(cur, parent);
                cur = parent;
            } else {
                break;
            }
        }
    }
    pop() {
        if (this.isEmpty()) return undefined;
        const root = this.heapq[1];
        const last = this.heapq.pop();
        if (this.isEmpty()) return last;
        this.heapq[1] = last;
        let cur = 1;
        while (cur < this.heapq.length) {
            let smallest = cur * 2;
            if (smallest >= this.heapq.length) break;

            let right = cur * 2 + 1;
            if (
                right < this.heapq.length &&
                this.heapq[smallest][0] > this.heapq[right][0]
            ) {
                smallest = right;
            }

            if (this.heapq[cur][0] > this.heapq[smallest][0]) {
                this.swap(cur, smallest);
                cur = smallest;
            } else {
                break;
            }
        }
        return root;
    }
}

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const [n, p, k] = input[0].split(' ').map(Number);

const gr = Array.from({ length: n + 1 }, () => []);
for (const [s, e, v] of input.slice(1).map((s) => s.split(' ').map(Number))) {
    gr[s].push([e, v]);
    gr[e].push([s, v]);
}

let start = 1;
let end = 1_000_000;
let answer = Infinity;
while (start <= end) {
    const pivotMoney = Math.floor((start + end) / 2);
    const visited = Array.from({ length: n + 1 }, () =>
        Array.from({ length: k + 1 }, () => Infinity)
    );

    const hq = new Heap();
    hq.push([0, 1, 0]);
    visited[1][0] = 0;
    let isTrue = false;
    while (!hq.isEmpty()) {
        const [maxMoney, cur, cntK] = hq.pop();
        if (cur === n) {
            answer = Math.min(maxMoney, answer);
            isTrue = true;
            break;
        }
        for (const [next, money] of gr[cur]) {
            if (next === 1) continue;
            if (money >= pivotMoney) {
                if (cntK === k) continue;
                if (visited[next][cntK + 1] <= maxMoney) continue;
                visited[next][cntK + 1] = maxMoney;
                hq.push([maxMoney, next, cntK + 1]);
            } else {
                const max = Math.max(maxMoney, money);
                if (visited[next][cntK] <= max) continue;
                visited[next][cntK] = max;
                hq.push([max, next, cntK]);
            }
        }
    }
    if (isTrue) {
        end = pivotMoney - 1;
    } else {
        start = pivotMoney + 1;
    }
}

if (answer === Infinity) {
    console.log(-1);
} else {
    console.log(answer);
}