読者です 読者をやめる 読者になる 読者になる

AOJ2445 MinimumCostPath

MinimumCostPath | Aizu Online Judge


まあまあ面白かった

n * n (n<=10^6)のマス目があって左下から右上に最短距離で行く場合の数(障害物は50個まで)

どう見てもスカスカで、殆ど邪魔されずに行けそうだけど左下と右上付近は混雑するかもしれないので、近くだけbfsして後はdp(経路を最初に通る障害物で区別したりするとなんとかなる)