問題 問題概要 グラフがあたえられる. 各頂点のいくつかはガソリンステーションでガソリンを入れることができる. ガソリンがなくならずに, スタートからゴールに行くまでの最短距離を求める. またLPGのタンクの最大容量もあたえられる. 車の燃費は10km/Lであ…

問題 問題概要 頂点1からNまでの最短コストを求めよ. ただし辺のコストtに加えて, 辺を通る時の色が決められているので, 色を変えるのにもコストがかかる. xからyに色を変える場合のコストは, |x-y|である. 解法 拡張ダイクストラをすればいい. dist[i][j]と…

問題 問題概要 最短経路を復元する。経路復元。 解法 ダイクストラでやる。経路復元は蟻本を参照。 気をつけることは、s->gの最短経路を求めるのではなく、今回は無向グラフであることを利用して、g->sへの最短経路を求め、そのついでにもとめられるpreを利…

問題 問題概要 省略 解法 一つの場所でできるだけ長く滞在すれば良い。できるだけ長く滞在するには、ある頂点iまで最短距離で行き、iからスタート時点まで最短距離で戻ってこればよい。そして残りの時間滞在すれば良いことになる。 求めるものは、0->iまでi-…

問題 問題概要 小麦屋さん以外の頂点でパン屋を開こうとする場合に、もっとも小麦屋さんから近くでパン屋を開ける頂点までの距離をもとめよ。開けないなら-1。 解法 ダイクストラで解いた。スタートをすべての小麦屋さんにして、それらの頂点からほかの頂点…

問題 問題概要 盤面に命令が書いてある。命令通りに行動すればコストは0。命令以外の行動をすれば、コストは指定された通りのコストがかかる。スタートからゴールまで行くのにかかる最短コストを求めよ。 解法 拡張ダイクストラで解いた。頂点の状態に番号だ…

問題 問題概要 スタートからゴールまで冷凍されたものを溶かさずにもっていけるかを求める問題。冷凍されたものは最大でm時間保存することができ、時間がたつと解ける。与えらた条件にある頂点で氷を冷凍することができる。溶かさずにゴールまで行く最短時間…

問題 問題概要 有向グラフが与えられる。1からnまで距離T以下で行く中で、辿る頂点の数を最大にする経路を求める。 解法 dpの解法は、dp[i][j] := i個の名所を回って、j番目の名所にいるときの、移動時間の最小値 として更新していけば解くことができた。今…

問題 問題概要 省略 解法 2分探索and最短経路問題。 xを小さくしていけば、かならず、ゴールにたどり着け、無限に大きくしていけば、どこかで、たどり着けなくなる。このような場合、求めるxを2分探索で効率よく絞り込んでいける。あとは、そのxに対して、ダ…

問題 問題概要 省略 解法 スタートからゴールにたどりつく方法が、スタートからゴールまでオアシスを使わずに行くか、オアシスを利用して、ゴールに行くかの2通りである。まず、スタートからゴールまでオアシスを使わずに、ゴールに行けるかを調べる。調べ方…

問題 問題概要 s->iへ到達できるか。ただし、通れる頂点に制約あり。 解法 思いついたのは、逆からunion-find。頂点iに行けるかを見る場合、i以上の頂点を使い、sからiへたどり着けるかを見れば良いので、i=n-1からi=0の順に調べ、そのつど、追加できる辺を…

問題 問題概要 複数のスタート場所があり、地点までの最短距離を求める。 解法 まず、ダイクストラを利用して、店から他の地点までの最短距離を入れる。このときの店というのは複数ある場合があるので、一番近い店からの距離を求めなければならない。最短距…

問題 問題概要 与えられたグラフに対して、幅優先探索を使い、条件を満たした新たなグラフを表す隣接行列を作り、ダイクストラで最小コストを作る。 解法 与えられたグラフのままでは、多くの条件あり、そのままではダイクストラをすることができない。そこ…

問題 問題概要 省略 解法 この問題は町どおしを有向グラフでつないでおり、現在の町の番号は増える方向に必ず増えるように条件が与えられている。そして、残り残金も減る方向に行くので、この問題はDAGグラフで考えることができ、dpで解くことが出来る。 dp[…