/** * 標準入力を受け取り、処理するための準備 * 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[]} 隣接リスト */ 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[]} 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();