なるほど。たしか、Dijkstra の定理を使えと言われたような気がします。
これって基本なんですかね？最短経路問題の。