test_longest_one-way_trip

問題：最長片道きっぷの旅

鉄道路線網（駅＝点、路線＝線）において、最も長い片道きっぷの経路を求めてください。

制約

• 同じ駅（点）を2回通ることはできません
• 始点・終点は全ての駅から自由に選択可能
  • （補足：独自条件）経路の途中で終点を通過して終点に戻ることは不可能とする
• 始点と終点が同じでもOK

入力フォーマット

各行に以下の形式で与えられます（標準入力）：

始点のID, 終点のID, 距離

• IDは正の整数、距離は浮動小数点数
• 数値の前後に任意の空白（スペース）が入る場合あり

入力例

1, 2, 8.54
2, 3, 3.11
3, 1, 2.19
3, 4, 4
4, 1, 1.4

出力フォーマット

最長経路となる駅のIDを、順番に1行ずつ（改行区切り）標準出力に出力してください。

解法

前提条件

• 同じ辺を2度通っても問題ない
  • 1-2-1のように遷移する場合は、同じ辺（最大の距離の辺）を用いる
• 同じ点同士を繋ぐ辺は一つではない可能性
  • グラフを構築するときに距離が大きい辺を保持

処理の流れ

1. グラフ構築
   • 標準入力から各行を (u, v, w) の形式で読み取る。
   • 各行は無向辺とみなし、u→v および v→u の両方向に登録する。
   • 同じ 2 頂点を結ぶ重複辺がある場合は、最大距離の 1 本のみを保持。
   • 構築された隣接リスト adj は、辺の重みが大きい順にソートされる（DFS 時に重い辺を優先的に試行するため）。
2. 全ノードを始点として DFS を実行
   • グラフ中の各頂点 s を始点として DFS を開始する。
   • 探索中は、visited 集合で訪問済みノードを管理し、同じ頂点の再訪を禁止。
   • DFS の途中で現在の経路長 length がこれまでの最長 best_len を超えた場合、最長経路とそのパスを記録。
   • 隣接ノードは重みの降順で探索し、早めに長い経路を見つけることで枝刈り効率を高める。
3. 始点に戻るサイクルも許容
   • len(path) >= 2 のときに限り、現在のノードから始点への戻りエッジが存在すればサイクルとして評価し、最長距離候補と比較する。
4. 枝刈り（Branch & Bound）による高速化
   • 各頂点 v に対して、incident（隣接）する最大辺長を best_inc[v] に保存しておく。
   • さらに全体での合計 total_inc を計算しておき、DFS の深さに応じて remain_inc（未訪問ノードの incident 最大辺長合計）を O(1) で更新しながら持ち回る。
   • 現在の経路長 length に、以下の要素を加えた上限を算出：

     upper = length + remain_inc + best_inc[start]
     

     • remain_inc: 未訪問ノードを通過できたとして伸びる可能性のある距離
     • best_inc[start]: 始点へ戻る 1 本の最大エッジの距離（閉路構築用）
   • この upper が既に best_len 以下であれば、それ以上の距離更新は不可能とみなし、その枝を探索から除外（剪定）する。