最短路を証明する木・経路の復元
最短距離の等式を満たす辺から、親・木・実現経路を選ぶ。
この典型を扱う単元: 最短路を証明する木・経路の復元
検索別名: path reconstruction、shortest-path tree、最短路木、経路復元
未知問からこの典型を見つける手掛かり
- 扱う対象
- parent
- 最短距離
- 経路
- 親辺
- 使う手掛かり
- 復元
- 木を構成
- 辺を出力
- 保つ不変量
- dist.*\+
- 最短路上
- 距離等式
- 求めるもの
- 構成
- 経路出力
- 辺の集合
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC252 E「Road Reduction」 公式問題主題: 最短路を証明する木・経路の復元 / 主タグ
- ABC218 F「Blocked Roads」 公式問題主題: 基準witnessから変更影響を局所化する / 主タグ
- ABC308 Ex「Make Q」 公式問題主題: 最短路モデル / 補助タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC218 F「Blocked Roads」 公式問題主題: 基準witnessから変更影響を局所化する / 主タグ
- ABC252 E「Road Reduction」 公式問題主題: 最短路を証明する木・経路の復元 / 主タグ
- ABC308 Ex「Make Q」 公式問題主題: 最短路モデル / 補助タグ
- ABC355 E「Guess the Sum」 公式問題主題: 状態グラフのモデリングと探索 / 補助タグ