GRL_1_C: All Pairs Shortest Path

重み付き有向グラフG=(V,E)の全点対間最短経路の距離を列挙してください

今回はヒントの絵があんまりヒントにならない気が
アイコンによると隣接行列と動的計画法を使うことになっているが

隣接行列って書いてあるのは隣接行列が特に便利っていう意味なんだろうか
今まであんまり隣接行列にして得になったイメージがないんだけれども
全頂点からの距離、ってことで行列をうまく使って一気に処理する、
ってことがないこともないかなあ

動的計画法を使うということは今までの結果をうまく使うということ
確かに今までに求めた最短距離が再利用可能ってことは普通に
ありそうだけれども

頂点が100個、辺が9,900個まである
始点と終点の組み合わせだけでも2乗のオーダだから
うまくやらないと間に合わなさそう
当然各頂点からダイクストラ法ってことはないんだろうなあ

マイナスの重みも許されてるところがまた
ぐるっと回ったら減ってたみたいなのを検出しなきゃいけない
という意味でもダイクストラ法は無理か

さっぱりアイデアがつながってこない感じ