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);
}