結果

問題 No.1473 おでぶなおばけさん
コンテスト
ユーザー Craft Boss
提出日時 2025-10-03 21:40:56
言語 JavaScript
(node v23.5.0)
結果
AC  
実行時間 1,808 ms / 2,000 ms
コード長 5,930 bytes
コンパイル時間 307 ms
コンパイル使用メモリ 7,972 KB
実行使用メモリ 106,288 KB
最終ジャッジ日時 2025-10-03 21:41:47
合計ジャッジ時間 43,651 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

diff # 

/**
 * 標準入力を受け取り、処理するための準備
 * Node.jsで競技プログラミングを行う際の定型文です。
 */
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin', 'utf8').trim();
const lines = input.split('\n');

/**
 * 町の連結関係を管理するためのUnion-Findクラス。
 */
class TownConnectivity {
    /**
     * @param {number} townNum 町の総数
     */
    constructor(townNum) {
        // 各要素の親を格納する配列。負の値の場合は、その要素が根（リーダー）であり、
        // その絶対値がグループのサイズを示す。
        this.parent = new Array(townNum + 1).fill(-1);
    }

    /**
     * 指定された町のリーダー（根）を見つける。
     * @param {number} townId 町のID
     * @returns {number} リーダーの町のID
     */
    find(townId) {
        if (this.parent[townId] < 0) {
            return townId;
        } else {
            // 経路圧縮：親をたどる過程で見つけた全てのノードを直接リーダーに繋ぎ変える
            this.parent[townId] = this.find(this.parent[townId]);
            return this.parent[townId];
        }
    }

    /**
     * 2つの町が含まれるグループを連結する。
     * @param {number} s 町sのID
     * @param {number} t 町tのID
     */
    union(s, t) {
        let sRoot = this.find(s);
        let tRoot = this.find(t);
        if (sRoot === tRoot) {
            return; // 既に同じグループなら何もしない
        }
        // Union by Size：サイズの小さいグループを大きいグループに連結する
        if (this.parent[sRoot] > this.parent[tRoot]) {
            [sRoot, tRoot] = [tRoot, sRoot]; // sRootが常に大きい方を指すようにスワップ
        }
        this.parent[sRoot] += this.parent[tRoot];
        this.parent[tRoot] = sRoot;
    }

    /**
     * 2つの町が連結しているか（同じグループか）を判定する。
     * @param {number} a 町aのID
     * @param {number} b 町bのID
     * @returns {boolean} 連結していればtrue
     */
    isConnected(a, b) {
        return this.find(a) === this.find(b);
    }
}

/**
 * 二分探索で、都市1とNが連結可能となる最大の耐久度wを求める。
 * @param {number[][]} roads 道のリスト [s, t, w]
 * @param {number} townNum 町の総数
 * @returns {number} 1とNを連結可能な最大の耐久度
 */
function findMaxW_binarySearch(roads, townNum) {
    let ok = 0; // この体重なら絶対に到達できる保証がある値
    let ng = roads[0][2] + 1; // この体重では絶対に到達できない保証がある値

    while (ng - ok > 1) {
        const mid = Math.floor((ok + ng) / 2);
        const connectivity = new TownConnectivity(townNum);

        // 耐久度がmid以上の道でunionしていく
        for (const [s, t, w] of roads) {
            if (w >= mid) {
                connectivity.union(s, t);
            } else {
                break; // roadsはソート済みなので、これ以上見る必要はない
            }
        }
        
        if (connectivity.isConnected(1, townNum)) {
            ok = mid; // 到達できるなら、midはOK。もっと上を目指す
        } else {
            ng = mid; // 到達できないなら、midはNG。もっと下を探す
        }
    }
    return ok;
}

/**
 * 辺リストを、指定された耐久度以上の道のみを含む隣接リストに変換する。
 * @param {number[][]} roads 道のリスト
 * @param {number} townNum 町の総数
 * @param {number} maxW 最小限必要な耐久度
 * @returns {Set<number>[]} 隣接リスト
 */
function convertEdgeToAdjacency(roads, townNum, maxW) {
    const adList = new Array(townNum + 1).fill(0).map(() => new Set());
    for (const [s, t, w] of roads) {
        if (w >= maxW) {
            adList[s].add(t);
            adList[t].add(s);
        } else {
            break;
        }
    }
    return adList;
}

/**
 * BFS（幅優先探索）で最短経路長を求める。
 * @param {number} townNum 町の総数
 * @param {Set<number>[]} adList 隣接リスト
 * @param {number} startNode スタート地点
 * @param {number} endNode ゴール地点
 * @returns {number} 最短経路長（到達不能なら-1）
 */
function findShortestPath(townNum, adList, startNode, endNode) {
    const queue = [startNode];
    const distance = new Array(townNum + 1).fill(-1);
    distance[startNode] = 0;

    while (queue.length > 0) {
        const currentTown = queue.shift();

        if (currentTown === endNode) {
            return distance[endNode];
        }

        for (const neighbor of adList[currentTown]) {
            if (distance[neighbor] === -1) {
                distance[neighbor] = distance[currentTown] + 1;
                queue.push(neighbor);
            }
        }
    }
    return -1;
}

/**
 * プログラムのメイン処理
 */
function main() {
    const [townNum, roadNum] = lines[0].split(' ').map(Number);

    // RE対策：道が一本もないエッジケースを処理
    if (roadNum === 0) {
        console.log(0, -1);
        return;
    }

    const roads = [];
    for (let i = 1; i <= roadNum; i++) {
        roads.push(lines[i].split(' ').map(Number));
    }

    // 耐久度の降順にソート
    roads.sort((a, b) => b[2] - a[2]);

    // 1. 二分探索で最大の耐久度wを求める
    const maxW = findMaxW_binarySearch(roads, townNum);
    
    // 2. maxWを使って隣接リストを作成
    const adList = convertEdgeToAdjacency(roads, townNum, maxW);
    
    // 3. BFSで最短経路を求める
    const minPath = findShortestPath(townNum, adList, 1, townNum);

    // 最終結果の出力
    console.log(maxW, minPath);
}

// スクリプトとして実行されたらmain関数を呼び出す
main();
0