結果

問題 No.1473 おでぶなおばけさん
コンテスト
ユーザー Craft Boss
提出日時 2025-10-03 21:39:20
言語 JavaScript
(node v23.5.0)
結果
AC  
実行時間 915 ms / 2,000 ms
コード長 5,684 bytes
コンパイル時間 246 ms
コンパイル使用メモリ 7,844 KB
実行使用メモリ 99,968 KB
最終ジャッジ日時 2025-10-03 21:39:52
合計ジャッジ時間 26,736 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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 findMaxWOptimized(roads, townNum) {
    const connectivity = new TownConnectivity(townNum);
    for (const [s, t, w] of roads) {
        connectivity.union(s, t);
        if (connectivity.isConnected(1, townNum)) {
            // 初めて連結した瞬間の耐久度が答え
            return w;
        }
    }
    return 0; // すべての道を使っても連結しなかった場合
}

/**
 * 辺リストを、指定された耐久度以上の道のみを含む隣接リストに変換する。
 * @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 {
            // roadsはソート済みなので、これ以上見る必要はない
            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]; // JSの配列をキューとして使用
    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);

    // エッジケース：道が一本もない場合
    if (roadNum === 0) {
        // N>=2 の制約より、到達は不可能
        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 = findMaxWOptimized(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