多クエリ対策。

ここのところ 1000 クエリを扱ってみて気づいたこととしては、クエリ数が増えていくにつれて同じ始点からの最短路を扱うこと必然的に増えてくる。

そういった際に複数回演算してしまうのは勿体ないので、別ルーチンにしようかと検討している。

「１対全最短路を解いてしまい、あとから必要なデータを抜き出す」か、
「すべての終点までの最短路を求めるまでで終了する」
という２パターンが考えられるが、前者を採用しようと思う。

理由としては、「１対全最短路は思ったより時間がかからなく」、「すべての終点まで最短路が求まった段階で終了するのでは、分岐の多くなってしまってかなりの低速化が起きてしてしまう」からである。また１対１最短路よりも実行時間の見積もりも立てやすい。もちろん単にコーディングが容易であるというメリットもある。