結果

問題 No.1473 おでぶなおばけさん
コンテスト
ユーザー Craft Boss
提出日時 2025-10-03 21:31:49
言語 JavaScript
(node v23.5.0)
結果
AC  
実行時間 950 ms / 2,000 ms
コード長 3,563 bytes
コンパイル時間 130 ms
コンパイル使用メモリ 7,972 KB
実行使用メモリ 99,460 KB
最終ジャッジ日時 2025-10-03 21:32:27
合計ジャッジ時間 28,836 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 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);
    }
}

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

// 最適化された方法で最大のwを見つける関数
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;
}

// 隣接リストを作成する関数
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 = findMaxWOptimized(roads, townNum);
    const adList = convertEdgeToAdjacency(roads, townNum, maxW);
    const minPath = findShortestPath(townNum, adList, 1, townNum);

    console.log(maxW, minPath);
}

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