グラフや盤面が時間変化する最短路問題
JOI
JOI予選・二次予選
JOI難易度5
AOJ
AtCoder
NoviSteps2Q
Dijkstra法
Floyd-Warshall法
クエリ処理問題
易しいクエリ処理問題
グラフ
クエリ(グラフ上)
【問題集】最短路問題
グラフや盤面が時間変化する最短路問題
最短路問題
操作:辺を追加する
取得:最大値・最小値
取得:最短路
実はクエリごとに毎回愚直に Dijkstra 法を回しても間に合う! 問題へのリンク 問題概要 最初、辺数 0 本、頂点数 個のグラフが与えられる。頂点番号は である。このグラフに対して 回のクエリが投げられる。 クエリタイプ 0:2 頂点 が指定されるので、頂点…
AtCoder
AtCoder450点
ABC-E
緑色diff
密グラフ
Dijkstra法
グラフ
最短路問題
【問題集】最短路問題
グラフや盤面が時間変化する最短路問題
DP状態:フェーズ(耳DP)
グラフテク:頂点を倍加する
典型要素を詰め合わせた教育的問題
最小コスト
所要時間を求める問題
最適化問題
少し頂点を増やす感じの Dijkstra 法。とても教育的な典型問題! 問題へのリンク 問題概要 頂点数 の完全グラフが与えられる。頂点 1 から頂点 へと到達したい。途中までは社用車を使い、途中からは電車を使うことができる。電車から社用車に乗り換えること…
AtCoder
AtCoder500点
unrated公式コン
迷路
二次元グリッド
グラフや盤面が時間変化する最短路問題
最短路問題
テク:循環するものを2週させる
操作列が文字列で与えられる
Greedy
最適化テク:解を変形していく(最適性を失わずに)
典型要素を詰め合わせた教育的問題
単調性に着目する
Greedy:今が良いほど未来も良い
壁マス
各地点に早くたどり着いておくに越したこと無い系問題!! atcoder.jp 問題概要 のグリッドがあってスタートからゴールへと行きたい。壁のあるマスは通れない。 ただし毎秒ごとに移動できる方向に制限がある。 で割ったあまりがそれぞれの場合についてどの方…
整数の三分探索は闇... 問題へのリンク 問題概要 頂点 辺の無向グラフが与えられる。時刻 0 に頂点 を出発し、頂点 まで移動するのに要する最小時間を求めよ。 各辺にはパラメータ が設定されていて、時刻 にその辺の片側の頂点から出発した場合、もう片側の…