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

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

• 計算量 が許されるので、毎回ダイクストラ法をする

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

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