重み付き最短路・経路復元・差分制約
概要
辺重みに応じた距離計算、距離等式による経路復元、差の不等式を緩和へ写す制約系への応用を順に学ぶ。
考え方
距離値は上界だけでは最短性を証明できない。各辺でd[v]≤d[u]+wとなる下界の条件と、実際に同じ長さの経路があることを合わせると最短距離の証拠になる。
成立条件と計算量
距離と前駆辺の検査はO(V+E)。到達不能頂点を有限距離と混ぜず、ゼロ重み辺で前駆関係がcycleにならないようにする。証拠を保持するとqueryや局所変更の影響を議論しやすくなる。
下位単元
- 最短路モデル — 緑色
- 最短路を証明する木・経路の復元 — 水色
- difference constraints・不等式系の最短路化 — 青色
問題一覧
この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC218 F「Blocked Roads」 公式問題
技能・出典
主題: 基準witnessから変更影響を局所化する(基準となる解や経路を証拠に、答えが変わり得る変更だけを特定して再計算を局所化できる。)。追加で学ぶ技能: 最短路を証明する木・経路の復元(距離等式を満たす親辺を選び、最短路の木または経路を復元できる。)。既習技能: 最短路モデル(非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。)。主タグ: 最短路を証明する木・経路の復元、基準解による変更影響の局所化 / 補助タグ: 最短路モデル
- ABC250 Ex「Trespassing Takahashi」 公式問題
技能・出典
主題: Kruskal順の閾値DSU sweep(同重みeventの順序を正しく定め、Kruskal順にDSU成分とmetadataを併合してminimax連結閾値でquery・pairing・集計を処理できる。)。追加で学ぶ技能: 最短路モデル(非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。)。既習技能: event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。) / DSUによる連結成分管理・縮約(静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。)。主タグ: Kruskal順の閾値DSU sweep、最短路モデル / 補助タグ: DSUによる連結成分管理・縮約、event・値順のオフライン走査
- ABC261 G「Replace」 公式問題主題: 区間合成・領域分割DP
技能・出典
主題: 区間合成・領域分割DP(区間や長方形の分割点を列挙し、独立な小領域の答えを合成して領域サイズ順に計算できる。)。既習技能: 最短路モデル(非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。)。主タグ: 区間合成・領域分割DP / 補助タグ: 最短路モデル
- ABC264 G「String Fair」 公式問題主題: 有限状態automatonの構成
技能・出典
主題: 有限状態automatonの構成(未来の一文字遷移を決める有限同値類を定義し、pattern suffix・subsequence進行・圧縮DP rowなどから完全遷移表を構成してDPや行列累乗に接続できる。)。追加で学ぶ技能: 最短路モデル(辺数を制限した反復緩和から負閉路・正閉路の検出を導き、始点到達性と終点への影響を区別できる。)。主タグ: 有限状態automatonの構成、最短路モデル
- ABC297 E「Kth Takoyaki Set」 公式問題
技能・出典
主題: priority queue・best-first列挙(現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 最短路モデル(非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。)。主タグ: priority queue・best-first列挙 / 補助タグ: 最短路モデル
- ABC299 E「Nearest Black Vertex」 公式問題主題: 成立証明から構成解を復元する
技能・出典
主題: 成立証明から構成解を復元する(成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。)。既習技能: 最短路モデル(非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。)。主タグ: 構成解・witness復元 / 補助タグ: 最短路モデル
- ABC301 E「Pac-Takahashi」 公式問題主題: 部分集合・bitmask状態DP
技能・出典
主題: 部分集合・bitmask状態DP(bitmaskの各bitが表す意味を定め、部分集合間の遷移を正しく設計できる。)。既習技能: 最短路モデル(非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。)。 BFSで重要地点間の距離を前計算し、移動の全履歴を距離へ圧縮する。その上でdp[S][v]から未訪問の代表地点へ進む部分集合DPを学び、最後に出口への距離を加えて時間制約を判定する。通過した菓子を全て状態に記録しなくても最適値を失わない理由も確かめる。主タグ: 部分集合・bitmask状態DP / 補助タグ: 最短路モデル
- ABC305 E「Art Gallery on Graph」 公式問題
技能・出典
主題: priority queue・best-first列挙(現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 最短路モデル(非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。)。主タグ: priority queue・best-first列挙 / 補助タグ: 最短路モデル
- ABC338 F「Negative Traveling Salesman」 公式問題主題: 部分集合・bitmask状態DP
技能・出典
主題: 部分集合・bitmask状態DP(bitmaskの各bitが表す意味を定め、部分集合間の遷移を正しく設計できる。)。既習技能: 最短路モデル(許す中継点集合を状態とするDPからFloyd–Warshallを導き、距離行列の更新順・到達不能・負閉路を扱える。)。 Floyd–Warshallで全点対距離を前計算し、最短路閉包上の訪問順を部分集合DPで学ぶ。maskは代表として訪問順へ追加した頂点集合であり、距離前計算の途中で通る頂点を禁止しない。任意のwalkから初訪問順を取り出す方向と、DP解をwalkへ展開する方向で同値性を示す。主タグ: 部分集合・bitmask状態DP / 補助タグ: 最短路モデル
- ABC355 E「Guess the Sum」 公式問題主題: 状態グラフのモデリングと探索
技能・出典
主題: 状態グラフのモデリングと探索(暗黙状態・重みなし辺・訪問条件を定義し、到達判定・最短手数・列挙の目的に応じてBFS・DFS・backtrackingを選べる。)。追加で学ぶ技能: 対話protocolを守って情報を取得する(judgeとの問い合わせ応答または交互手番のprotocolを守り、許された形式で応答依存の探索・合法手の提示・終了処理を実行できる。query上限がある場合はその回数も満たす。)。既習技能: 最短路を証明する木・経路の復元(距離等式を満たす親辺を選び、最短路の木または経路を復元できる。)。主タグ: 対話protocolとquery設計、状態グラフのモデリングと探索 / 補助タグ: 最短路を証明する木・経路の復元
- ABC364 G「Last Major City」 公式問題
技能・出典
主題: Steiner tree subset DP(terminal subsetと終点を状態に、subset分割mergeとmulti-source shortest path relaxationを交互に行う。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 最短路モデル(非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。)。主タグ: Steiner tree subset DP / 補助タグ: 最短路モデル
- ABC369 E「Sightseeing Tour」 公式問題
技能・出典
主題: 候補数を界して全列挙・有限case分解する(制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。)。既習技能: 最短路モデル(許す中継点集合を状態とするDPからFloyd–Warshallを導き、距離行列の更新順・到達不能・負閉路を扱える。)。主タグ: 有界全列挙・有限case分解 / 補助タグ: 最短路モデル
- ABC375 F「Road Blocked」 公式問題主題: 時間を逆向きにして未来依存を消す
技能・出典
主題: 時間を逆向きにして未来依存を消す(時間依存を逆走査・逆操作・last-write時刻で単調または静的にし、元の時点へ答えを戻せる。)。既習技能: 最短路モデル(許す中継点集合を状態とするDPからFloyd–Warshallを導き、距離行列の更新順・到達不能・負閉路を扱える。)。主タグ: 逆向きのオフライン処理 / 補助タグ: 最短路モデル
- ABC375 G「Road Blocked 2」 公式問題
技能・出典
主題: lowlinkで橋・関節点を特定する(DFS木の到達時刻とlowlink値を計算し、橋と関節点の判定条件を説明できる。)。既習技能: 最短路モデル(非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。)。 両端からのDijkstraで距離を前計算し、d_s[u]+w(u,v)+d_t[v]=d_s[t]を満たす辺だけで最短路部分グラフを作る。そのグラフでlowlinkによる橋判定を学び、橋と全最短路に不可欠な辺を対応させる。元グラフの橋判定とは違う。正重みによる距離の増加を使って対応を証明する。主タグ: lowlinkによる橋・関節点の検出 / 補助タグ: 最短路モデル
- ABC393 G「Unevenness」 公式問題
技能・出典
主題: Lagrangian relaxation・Aliens trick(個数制約へpenalty λを加えたoracleで双対下界を求める。厳密復元には個数別最適値の離散凸性などから対象個数で双対ギャップがないことを証明し、その上で個数単調性とtie-breakにより支持直線を探索する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 連分数・Stern–Brocotで有理近似する(Euclid互除法・連分数・Stern–Brocotの区間を使い、分母上限下の最良有理近似を求められる。) / 最短路モデル(辺数を制限した反復緩和から負閉路・正閉路の検出を導き、始点到達性と終点への影響を区別できる。) / 最小費用流・circulation(流量と費用を持つ残余networkを設計し、potential付き最短路・slope・cycle cancelingで流量別最小費用を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: Lagrangian relaxation・Aliens trick / 補助タグ: 最小費用流・circulation、連分数・Stern–Brocot有理近似、最短路モデル
- ABC395 G「Minimum Steiner Tree 2」 公式問題
技能・出典
主題: Steiner tree subset DP(terminal subsetと終点を状態に、subset分割mergeとmulti-source shortest path relaxationを交互に行う。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 最短路モデル(非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。)。主タグ: Steiner tree subset DP / 補助タグ: 最短路モデル
- ABC429 F「Shortest Path Query」 公式問題主題: 区間monoid要約
技能・出典
主題: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。)。既習技能: 半環行列・min-plus/max-min遷移(遷移を半環行列として定義し、結合則と単位元を保つ二分累乗・区間積で巨大回数の最適化遷移を計算できる。) / 最短路モデル(DAGや使用可能な辺列の順に緩和し、処理済みprefixが表す経路集合を不変量として説明できる。)。主タグ: 区間monoid要約 / 補助タグ: 半環行列・min-plus/max-min遷移、最短路モデル
前提・学習成果・出典
導入対象の目安: 緑色(800–1199)。辺の重みに合う距離計算を選び、最短路の復元へ進む入口。
対象色の読み方は本書の読み方を参照してください。
概念上の親: グラフアルゴリズム。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-shortest-path-certificates
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: なし。
このUnitを直接前提とする単元: なし。
このUnitでは扱わないもの
- 辺重みや最短距離を扱わず、到達可否だけを求める探索、および最短路に限らない一般の変更影響解析。