頂点倍化
いわゆる拡張ダイクストラ法。
同じ頂点の異なる状態をそれぞれ別の頂点として考えて、拡張したグラフ上で問題を解く。