問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0519 解法 a が b に勝利したことを，a -> b と有向辺で表現することにすれば，この問題はトポロジカル順序を求める問題になる． トポロジカル順序が求まったら，その頂点列のなかで隣り合っ…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0526 解法 基本はワーシャルフロイドだが，それだと間に合わないので工夫する． 仮に島a, b間の船舶が更新された時，グラフ上の異なる2つの島u, vの最短経路は， u -> a -> b -> v つまり d[…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0562 解法 まず，各頂点がショッピングモールからどれだけ離れているかを求める． これは，ショッピングモールの頂点をあらかじめ全てpriority_queueに突っ込んでおいたダイクストラを解けば…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0623 解法 危険な街を列挙さえすれば，あとはただの単一始点最短路問題． 危険な街を列挙するには，ゾンビに支配された街を全て，最初にqueueにプッシュしておくだけで十分である．計算量…