ABC291 F - Teleporter and Closed off (500)
テレポーターは都市の番号が大きくなるようにしか移動できない
テレポーターとその逆向きにそれぞれ辺を張る
DPで各都市から都市1、都市Nへ移動コストの最小値を求めておく
$ \mathcal{O}(NM)で$ M \le 10なので早い
各点についてその$ M-1個前から1個前までの間で$ kを飛ばしてテレポーターを使ったときの都市1からNまでの最小値を求める
こっちは$ \mathcal{O}(NM^2)
問題: https://atcoder.jp/contests/abc291/tasks/abc291_f
提出: https://atcoder.jp/contests/abc291/submissions/39245715
#ABC291 #500pt #F #ABC #AtCoder
#O(NM^2)