AOJ

まあまあ面白かった

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

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

gdgdiary

AOJ2445 MinimumCostPath