题目链接
Solution
当 $k$ 是奇数时，肯定无法回到原点，所以只用考虑 $k$ 是偶数的情况。很显然，从 $u$ 回到其本身的最优路径一定是先从 $u$ 走 $k/2$ 步到某个 $v$，再从 $v$ 原路返回 走 $k/2$ 步到 $u$。所以问题转化为对每个点求走 $k/2$ 步的最短路（不管最后走到哪里），答案就是这个长度乘 $2$。设 $dp[i][j][t]$ 表示从 $(i,j)$ 出发走了 $t$ 步到达终点的最短路长度，则 $dp[i][j][t]$ 可以从 $dp[i-1][j][t+1],\,dp[i+1][j][t+1],\,dp[i][j-1][t+1],\,dp[i][j+1][t+1]$ 四个方向转移而来，初始条件是 $dp[i][j][k/2]=0$.
当然如果想看得更直观一点，可以想象一个 $k$ 层的分层图，那么我们求的就是从第 $0$ 层走到第 $k$ 层任意一个节点的最短路。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
const int N = 505;
int n, m, k;
LL a[N][N], b[N][N], dp[N][N][25];
int main(){
read(n, m, k);
for(int i = 1; i <= n; i++)
for(int j = 1; j < m; j++)
read(a[i][j]);
for(int i = 1; i < n; i++)
for(int j = 1; j <= m; j++)
read(b[i][j]);
if(k & 1){
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
printf("%d%c", -1, " \n"[j==m]);
return 0;
}
k >>= 1;
memset(dp, 0x7f, sizeof dp);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
dp[i][j][k] = 0;
for(int kk = k - 1; kk >= 0; kk--){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(i < n) dp[i+1][j][kk] = min(dp[i][j][kk+1] + b[i][j], dp[i+1][j][kk]);
if(i > 1) dp[i-1][j][kk] = min(dp[i][j][kk+1] + b[i-1][j], dp[i-1][j][kk]);
if(j < m) dp[i][j+1][kk] = min(dp[i][j][kk+1] + a[i][j], dp[i][j+1][kk]);
if(j > 1) dp[i][j-1][kk] = min(dp[i][j][kk+1] + a[i][j-1], dp[i][j-1][kk]);
}
}
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
printf("%lld%c", dp[i][j][0] * 2, " \n"[j == m]);
return 0;
}
|