次のような \(2N\) 頂点 \(N + 2M\) 辺の有向グラフ（辺にのみコストあり）を作ると、頂点 \(1_\text{in}\) から頂点 \(i_\text{out}\) までの経路の最小コストが求めるものです。

• 元のグラフの各頂点 \(i\) に対し、二つの頂点 \(i_\text{in}\) と \(i_\text{out}\) を作り、コスト \(A_i\) の有向辺 \(i_\text{in} \to i_\text{out}\) を張る。
• 元のグラフの各辺 \(u \leftrightarrow v\) に対し、同コストの二本の有向辺 \(u_\text{out} \to v_\text{in}\) と \(v_\text{out} \to u_\text{in}\) を張る。

この最小コストはダイクストラ法で \(O(M \log N)\) 時間で求められます。（公式解法より定数倍が大きいですが、この手法は他の用途にも使えます。）