ツバサの備忘録

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

ワーシャル-フロイド法

ABC051 D - Candidates of No Shortest Paths

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

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

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

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

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