船旅(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