結果

問題 No.1473 おでぶなおばけさん
コンテスト
ユーザー Craft Boss
提出日時 2025-10-03 21:36:36
言語 JavaScript
(node v23.5.0)
結果
RE  
実行時間 -
コード長 4,614 bytes
コンパイル時間 303 ms
コンパイル使用メモリ 7,844 KB
実行使用メモリ 78,192 KB
最終ジャッジ日時 2025-10-03 21:36:58
合計ジャッジ時間 19,027 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 2
other RE * 47
権限があれば一括ダウンロードができます

ソースコード

diff # 

// 標準入力を受け取るための準備
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin', 'utf8').trim();
const lines = input.split('\n');

// --- TownConnectivity クラス (Union-Find) ---
class TownConnectivity {
    // コンストラクタ (__init__ に相当)
    constructor(townNum) {
        // this は Python の self に相当
        this.parent = new Array(townNum + 1).fill(-1);
    }

    // リーダーを見つける find メソッド
    find(townId) {
        if (this.parent[townId] < 0) {
            return townId;
        } else {
            // 経路圧縮
            this.parent[townId] = this.find(this.parent[townId]);
            return this.parent[townId];
        }
    }

    // 2つのグループを連結する union メソッド
    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]; // swap
        }
        this.parent[sRoot] += this.parent[tRoot];
        this.parent[tRoot] = sRoot;
    }

    // 連結しているか確認する isConnected メソッド
    isConnected(a, b) {
        return this.find(a) === this.find(b);
    }
}

// --- 各処理の関数 ---

// findMax_wのJavaScriptバージョン
function findMaxW_binarySearch(roads, townNum) {
    // ok: この体重なら絶対に到達できる保証がある値
    let ok = 0;
    // ng: この体重では絶対に到達できない保証がある値
    // roads[0][2]はソート後の最大耐久度
    let ng = roads[0][2] + 1;

    // okとngの差が1になるまで繰り返す
    while (ng - ok > 1) {
        // 中央値を計算
        const mid = Math.floor((ok + ng) / 2);
        
        // midの体重で到達可能か調べる
        const connectivity = new TownConnectivity(townNum);
        
        // 耐久度がmid以上の道でunionしていく
        for (const [s, t, w] of roads) {
            if (w >= mid) {
                connectivity.union(s, t);
            } else {
                // roadsはソート済みなので、これ以上見る必要はない
                break;
            }
        }
        
        // 都市1と終点が連結しているかチェック
        if (connectivity.isConnected(1, townNum)) {
            // 到達できる => midはOKな値。もっと上を目指す
            ok = mid;
        } else {
            // 到達できない => midはNGな値。もっと下を探す
            ng = mid;
        }
    }
    
    // ループ終了後、答えは必ず ok に入っている
    return ok;
}

// 隣接リストを作成する関数
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で最短経路を見つける関数
function findShortestPath(townNum, adList, startNode, endNode) {
    // JSの配列をキューとして使う (pushで追加, shiftで取り出し)
    const queue = [startNode];
    const distance = new Array(townNum + 1).fill(-1);
    distance[startNode] = 0;

    while (queue.length > 0) {
        const currentTown = queue.shift(); // 先頭から取り出す (popleft)

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

        for (const neighbor of adList[currentTown]) {
            if (distance[neighbor] === -1) {
                distance[neighbor] = distance[currentTown] + 1;
                queue.push(neighbor); // 末尾に追加 (append)
            }
        }
    }
    return -1; // 到達不能
}

// --- メイン処理 ---
function main() {
    // 最初の行から townNum と roadNum を読み取る
    const [townNum, roadNum] = lines[0].split(' ').map(Number);
    const roads = [];
    for (let i = 1; i <= roadNum; i++) {
        roads.push(lines[i].split(' ').map(Number));
    }

    // wの降順にソート
    // (a, b) => b[2] - a[2] は Pythonの key=lambda x:x[2], reverse=True と同じ
    roads.sort((a, b) => b[2] - a[2]);

    const maxW = findMaxW_binarySearc(roads, townNum);
    const adList = convertEdgeToAdjacency(roads, townNum, maxW);
    const minPath = findShortestPath(townNum, adList, 1, townNum);

    console.log(maxW, minPath);
}

// スクリプトの実行
main();
0