CF1517D Explorer Space
题意简述：
给定一个 n×m 的四联通带权网格图，对于每个格点求恰好k 步回到自身的最短路径，若无法到达，输出 −1 。
题解：
首先考虑无解的情况：显然k为奇数的情况时无解。
有解的情况下最优方案应该是选定一个长度为的路径，出去再回来。这样题意就变成从一个点出发，寻找一个长度为
的最短路径。显然可以dp。
我们设dp[i][j][l]表示从(i,j)出发，走了l步的最小取值。
r[i][j]表示(i,j)与(i,j+1)之间的边权。
d[i][j]表示(i,j)与(i+1,j)之间的边权。 其中r数组和d数组是输入的。
先上代码
for(int l=1;l<=(k/2);l++){ for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ dp[i][j][l]=INT_MAX; if(j>1) dp[i][j][l]=min(dp[i][j][l],dp[i][j-1][l-1]+r[i][j-1]); if(j<m) dp[i][j][l]=min(dp[i][j][l],dp[i][j+1][l-1]+r[i][j]); if(i>1) dp[i][j][l]=min(dp[i][j][l],dp[i-1][j][l-1]+d[i-1][j]); if(i<n) dp[i][j][l]=min(dp[i][j][l],dp[i+1][j][l-1]+d[i][j]); } } }这四条转移分别是从左，右，上，下转移过来。这个挺好理解的。然后l只到k/2。
输出要记得乘二。
for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ printf("%d ",dp[i][j][k/2]*2); } printf("\n"); }完整代码（带注释）
#include<bits/stdc++.h> using namespace std; const int N=5e2+5,K=25; int n,m,k,r[N][N],d[N][N],dp[N][N][K];//设dp[i][j][l]表示从(i,j)出发，走了l步的最小取值。 //r[i][j]表示(i,j)与(i,j+1)之间的边权。 //d[i][j]表示(i,j)与(i+1,j)之间的边权。 int main(){ scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++){ for(int j=1;j<m;j++){ scanf("%d",&r[i][j]); } } for(int i=1;i<n;i++){ for(int j=1;j<=m;j++){ scanf("%d",&d[i][j]); } } if(k%2==1){ for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ printf("-1 "); } printf("\n"); } return ~(-1); } //设dp[i][j][l]表示从(i,j)出发，走了l步的最小取值。 //r[i][j]表示(i,j)与(i,j+1)之间的边权。 //d[i][j]表示(i,j)与(i+1,j)之间的边权。 /* (i-1,j) (i,j-1) (i,j) (i,j+1) (i+1,j) */ for(int l=1;l<=(k/2);l++){ for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ dp[i][j][l]=INT_MAX; if(j>1) dp[i][j][l]=min(dp[i][j][l],dp[i][j-1][l-1]+r[i][j-1]); if(j<m) dp[i][j][l]=min(dp[i][j][l],dp[i][j+1][l-1]+r[i][j]); if(i>1) dp[i][j][l]=min(dp[i][j][l],dp[i-1][j][l-1]+d[i-1][j]); if(i<n) dp[i][j][l]=min(dp[i][j][l],dp[i+1][j][l-1]+d[i][j]); } } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ printf("%d ",dp[i][j][k/2]*2); } printf("\n"); } return ~(-1); }