結果
| 問題 | No.1473 おでぶなおばけさん | 
| コンテスト | |
| ユーザー |  | 
| 提出日時 | 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 | 
ソースコード
/**
 * 標準入力を受け取り、処理するための準備
 * 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();
            
            
            
        