問題 問題概要 最短経路を復元する。経路復元。 解法 ダイクストラでやる。経路復元は蟻本を参照。 気をつけることは、s->gの最短経路を求めるのではなく、今回は無向グラフであることを利用して、g->sへの最短経路を求め、そのついでにもとめられるpreを利…

問題 問題概要 任意のマスからスタートして、数字の大きい方へ進める。経路の総数を求める。 解法 dp[i][j]:= y=i,x=jから始めた時の経路の総数 として、再帰関数を用いて、周りの4方向どこへも進めないマスから順に埋めていけばいい。メモ化しておけばTLEに…