ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ワーシャル-フロイド法

ARC099 E - Independence

問題 提出コード 解法 頂点との間に辺が張られていない場合、これらを同じ州に含めることができません。 これは全ての張られていない辺について成り立ちます。逆に、同じ州に含めることができない頂点対に辺を張ったグラフを考えると(これは与えられるグラフ…

AOJ 2200 - Mr. リトー郵便局

問題 提出コード 解法 まずは、陸路と海路それぞれについて、ワーシャルフロイド法を用いて、任意の町間の最短距離を計算しておきます。町から町の最短経路について、陸路を、海路をとします。 そして、DPを行います。 回目の集配を終えた時点で、船が町にあ…

AOJ 2005 - Water Pipe Construction

問題 提出コード 解法 設置コストを辺の距離とみなすと、結局何かしらの距離の最小値を求めるような問題に帰着できそうな気がします。ここで、制約に注目すると、が100以下であり、[tex:O(N3)]が通ることから、ワーシャルフロイド法が使えそう、ということが…

AOJ 2021 - お姫様の危機

問題 提出コード 解法 町の数が少ないので、まずは任意の2つの町を結ぶ最短経路を求めます。これは、ワーシャルフロイドを利用すれば簡単に求めることができます。 あとは、スタート地点から、今いる地点から分以内で行ける、冷凍施設のある町のみを経由して…

ABC022 C - Blue Bird

問題 提出コード1 提出コード2 解法 まずは想定解です。 頂点1から出るときの辺と、頂点1に帰るときの辺は違うものでなくてはなりません。 そのときの頂点をとすると、からは純粋な最短経路問題に置き換えることができます。 この問題では、頂点の個数が300…

ABC079 D - Wall

問題 提出コード 解法 1つのマス目が、他のマス目に影響を及ぼすことも、影響されることもないので、それぞれのマスについて、-1でない場合に1へと変化させる魔力の最小値を求めればよいです。 ということで、マス目の現在の数字(0~9)を頂点、をからへ向かう…

ABC074 D - Restoring Road Network

問題 提出コード 解法 まずは、答えが-1、つまり入力された値で条件を満たすグラフを作成できるかどうかの判定をします。 これは、ワーシャルフロイド法を用いて行うことができます。行った結果、すべての距離が更新されることがなかった場合、条件を満たす…

ABC073 D - joisino's travel

問題 提出コード 典型+久々につかう知識問題。 解法 まずは、頂点数が200しかないので、が間に合います。ので、とりあえずワーシャルフロイド法を適用し、それぞれの頂点間の距離の最小値を求めておきます。 そして、通りたい頂点数は8しかないので、全探索…

ABC051 D - Candidates of No Shortest Paths

問題 提出コード 解法 ,を距離で通る辺が使用されるには、との最短距離がになっていればいいです。最短距離になっていない場合、とを通るより最短距離になっているルートを通る方がいかなる場合にも距離が短くなるため、とにおいての最短距離がかどうかだけ…

ABC012 D - バスと避けられない運命

D - バスと避けられない運命 提出コード ワーシャル-フロイド法を利用して、バス停iからバス停jに行くための最短時間をですべて記録します。 終わったら、バス停iについて、そこからバス停jに行くまでの最悪時間を、jで全探索してiごとに記録します。 あとは…

京都大学プログラミングコンテスト(KUPC)2013

競プロの練習会で、こちらのセットを使用したバチャコンをチームで行ったので解いた問題についてのメモをしていきます。 チームメイトはICPC出場時と同じくやまさん(@yamasangamasan)、べるくん(@dora_marutation)でした。加えて、相手チームがICPC本戦出場…