题意
有一个$n \times m$的棋盘。相邻两个各自都有边，每条边都有一个长度。
现在问你，从任意点$(i,j)$出发，走$k$步后回到$(i,j)$所经过的最小长度是多少。过程中可以多次路过$(i,j)$。
题解
首先如果$k$不是偶数，必然无解。
定义$map[i][j][d]$（其中$0 \leq d < 4$）表示$(i,j)$往四个方向的边长。
定义$dp[p][i][j]$表示，从$(i,j)$出发，走$2\cdot p$步回到$(i,j)$的最小开销。
于是有$$dp[p][i][j]=\min\limits_{0 \leq d < 4} dp[p-1][next_i][next_j]+map[i][j][d]$$其中$next_i$，$next_j$表示从$(i,j)$往$d$方向走一步的坐标。
代码
Submission #114076615 - Codeforces
Codeforces. Programming competitions and contests, programming community
