最短路モデル
重み付きグラフの距離を計算し、距離の確定条件や最短路木の枝構造から経路・閉路の最適化を行う。
この典型を扱う単元: 最短路モデル
検索別名: Bellman–Ford法、Dijkstra法、shortest path、最短経路
未知問からこの典型を見つける手掛かり
- 扱う対象
- dijkstra
- distance
- path
- コスト
- 距離
- 辺
- 道
- 重み
- 使う手掛かり
- frontier
- multi.?source
- threshold
- 最小コスト
- 最短
- 移動
- 保つ不変量
- dist
- priority queue
- 確定したvertex
- 緩和
- 距離確定
- 求めるもの
- 最小コスト
- 最小時間
- 最短距離
- 適用しない条件
- syntax
- 最短(式|文字列)
- 構文
分類・前提・学習成果
分類と直接の前提
概念上の親: グラフモデルと構造
関連する典型
- 状態グラフのモデリングと探索: 問題状態を頂点、合法操作を辺へ写してから、辺重みに応じた最短路algorithmを選ぶ流れで併用する。
学習成果と学習単位
許す中継点集合を状態とするDPからFloyd–Warshallを導き、距離行列の更新順・到達不能・負閉路を扱える。
最短路モデルで学ぶ辺数を制限した反復緩和から負閉路・正閉路の検出を導き、始点到達性と終点への影響を区別できる。
最短路モデルで学ぶ根からの最短路木で第一枝の異なる頂点を結ぶ辺を列挙し、二本の木上経路と合わせて根を通る最小閉路を求められる。
最短路モデルで学ぶ非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。
最短路モデルで学ぶDAGや使用可能な辺列の順に緩和し、処理済みprefixが表す経路集合を不変量として説明できる。
最短路モデルで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC213 E「Stronger Takahashi」 公式問題主題: 最短路モデル / 主タグ
- ABC237 E「Skiing」 公式問題主題: 最短路モデル / 主タグ
- ABC271 E「Subsequence Path」 公式問題主題: 最短路モデル / 主タグ
- ABC325 E「Our clients, please wait a moment」 公式問題主題: 最短路モデル / 主タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC213 E「Stronger Takahashi」 公式問題主題: 最短路モデル / 主タグ
- ABC218 F「Blocked Roads」 公式問題主題: 基準witnessから変更影響を局所化する / 補助タグ
- ABC232 G「Modulo Shortest Path」 公式問題主題: 最短路モデル / 主タグ
- ABC237 E「Skiing」 公式問題主題: 最短路モデル / 主タグ
- ABC243 E「Edge Deletion」 公式問題主題: 最短路モデル / 主タグ
- ABC243 Ex「Builder Takahashi (Enhanced version)」 公式問題主題: 最短路モデル / 主タグ
- ABC245 G「Foreign Friends」 公式問題主題: 最短路モデル / 主タグ
- ABC246 E「Bishop 2」 公式問題主題: 最短路モデル / 主タグ
- ABC250 Ex「Trespassing Takahashi」 公式問題主題: Kruskal順の閾値DSU sweep / 主タグ
技能・出典
主タグ: Kruskal順の閾値DSU sweep、最短路モデル / 補助タグ: DSUによる連結成分管理・縮約、event・値順のオフライン走査
- ABC252 E「Road Reduction」 公式問題主題: 最短路を証明する木・経路の復元 / 補助タグ
- ABC257 F「Teleporter Setting」 公式問題主題: 最短路モデル / 主タグ
- ABC261 G「Replace」 公式問題主題: 区間合成・領域分割DP / 補助タグ
- ABC264 G「String Fair」 公式問題主題: 有限状態automatonの構成 / 主タグ
- ABC271 E「Subsequence Path」 公式問題主題: 最短路モデル / 主タグ
- ABC277 E「Crystal Switches」 公式問題主題: 最短路モデル / 主タグ
- ABC286 E「Souvenir」 公式問題主題: 最短路モデル / 主タグ
- ABC291 F「Teleporter and Closed off」 公式問題主題: 最短路モデル / 主タグ
- ABC297 E「Kth Takoyaki Set」 公式問題主題: priority queue・best-first列挙 / 補助タグ
- ABC299 E「Nearest Black Vertex」 公式問題主題: 成立証明から構成解を復元する / 補助タグ
- ABC301 E「Pac-Takahashi」 公式問題主題: 部分集合・bitmask状態DP / 補助タグ
- ABC305 E「Art Gallery on Graph」 公式問題主題: priority queue・best-first列挙 / 補助タグ
- ABC307 F「Virus 2」 公式問題主題: 最短路モデル / 主タグ
- ABC308 Ex「Make Q」 公式問題主題: 最短路モデル / 主タグ
- ABC325 E「Our clients, please wait a moment」 公式問題主題: 最短路モデル / 主タグ
- ABC338 F「Negative Traveling Salesman」 公式問題主題: 部分集合・bitmask状態DP / 補助タグ
- ABC342 E「Last Train」 公式問題主題: 最短路モデル / 主タグ
- ABC364 G「Last Major City」 公式問題主題: Steiner tree subset DP / 補助タグ
- ABC369 E「Sightseeing Tour」 公式問題主題: 候補数を界して全列挙・有限case分解する / 補助タグ
- ABC375 F「Road Blocked」 公式問題主題: 時間を逆向きにして未来依存を消す / 補助タグ
- ABC375 G「Road Blocked 2」 公式問題主題: lowlinkで橋・関節点を特定する / 補助タグ
- ABC393 G「Unevenness」 公式問題主題: Lagrangian relaxation・Aliens trick / 補助タグ
- ABC395 E「Flip Edge」 公式問題主題: 最短路モデル / 主タグ
- ABC395 G「Minimum Steiner Tree 2」 公式問題主題: Steiner tree subset DP / 補助タグ
- ABC414 G「AtCoder Express 4」 公式問題主題: 最短路モデル / 主タグ
- ABC416 E「Development」 公式問題主題: 最短路モデル / 主タグ
- ABC429 F「Shortest Path Query」 公式問題主題: 区間monoid要約 / 補助タグ
- ABC431 E「Reflection on Grid」 公式問題主題: 最短路モデル / 主タグ
- ABC463 E「Roads and Gates」 公式問題主題: 最短路モデル / 主タグ