船旅(08予選6)
N個の島とK個のクエリが与えられる。
(1<=N<=100,1<=K<=5000)
クエリの種類は2種類で、
①島Bから島Cへ移動する際の最短コストを求める。
②島Bと島Cの間にコストDの双方向に移動できる辺を置く
また、開始時点では辺は存在しない
辺の追加はO(1)、最短コストはO(N^2)で求められる。
よってO(KN^2)のため間に合う。
(辺の追加回数上限が設定されているのでもしかするとdijkstraの高速化が要求されていた時代かもしれない…?)
難易度は4程度に感じられた……がdijkstraは5以上かなあと思うので5にしておく
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2243185#1