第二回 PAST H - 1-9 Grid ダイクストラ解法

Quiz

https://atcoder.jp/contests/past202004-open/tasks/past202004_h

AC code

https://atcoder.jp/contests/past202004-open/submissions/13146204

解法

  • 始点を0, 終点を10とします
  • 各グリッドの位置ごとにidを振っておきます
  • 数値 i -> 数値 i+1 のそれぞれのペアに、マンハッタン距離をコストとした辺をはります
  • SからEへのダイクストラすると答えが求まります

f:id:peroon:20200512172521p:plain