7K12 blog

猫でも分かるアルゴリズム解説

AOJ2008 第7回日本情報オリンピック 予選 F - 船旅

f:id:tkr987:20200627014907p:plain

https://atcoder.jp/contests/joi2008yo/submissions/10331886

f:id:tkr987:20200627015019p:plain

グラフアルゴリズムの基本問題。制約から辺の本数が最大で 10^3、頂点数が最大で 10^2しかないので、 O(N^2)でもTLEしない。したがって、注文票クエリ毎にダイクストラ法をすることで答えが得られる。正確には全体計算量は O( K (V+E) \log V )となる。

新たな運航があった時に双方向に辺を張ることを忘れずに。