Problem Statement
染染船长，扬帆起航！
在一系列准备工作做完后，染染的船终于出发了。
没过多久，染染就来到了一片复杂的海洋。这片海洋可以看成一个 n×m 的网格，网格上的每个格点代表了一片海域。直线通过第 i 行第 j 列的海域需要花费 $t_{i,j}$ 的时间。除此之外，如果需要转向，还需要额外花费 $d_{i,j}$ 的时间，当然不管向左转向右转还是掉头都需要额外花费 $d_{i,j}$的时间。也就是说，如果要通过第 i 行第 j 列的海域并且中途转向，则需要花费 $t_{i,j}+d_{i,j}$的时间。
规定右方向为列增加的方向，下方向为行增加的方向。染染一开始向右驶入了这片海洋第 1 行第 1 列的海域，他想要从第 n 行第 m 列的海域向下驶出这片海洋，最快需要花费多少时间？
注意，通过这片海洋第 1 行第 1 列的海域和第 n 行第 m 列的海域花费的时间也要计算。
本题单个测试点内包含多组测试数据。
输入第一行一个正整数 T (1≤T≤20)T (1≤T≤20)，表示数据组数。
每组数据第一行两个正整数 n,m (1≤n×m≤105)n,m (1≤n×m≤105)，分别表示这片海洋的行数和列数。
接下来 n 行，第 i 行 m个非负整数 $(0≤t_{i,j}≤10^{9})$，表示直线通过的时间花费。
接下来 n 行，第 i 行 m 个非负整数$(0≤d_{i,j}≤10^{9})$,表示转向的时间花费。
保证单个测试点内每组数据中 n×m 的和不超过 $10^{6}$。
Output
对于每组数据输出一行一个非负整数，表示花费的最少时间。
1
2
3
4
5
6
7
8
9
10
11
|
2
1 1
1
1
3 3
1 1 1
1 2 1
1 1 1
0 999 999
0 0 999
999 0 0
|
Sample Output
Explanation of Example
对于第一组样例，染染只需要转向通过第 11 行第 11 列的海域，花费时间 1+1=21+1=2。
对于第二组样例，染染要依次经过第 11 行第 11 列、第 22 行第 11 列、第 22 行第 22 列、第 33 行第 22 列、第 33 行第 33 列并在经过的每片海域处转向，花费时间 66。
Solving
拆点最短路的模板题:
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
|
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
//2025 杭州电子科技大学 春季多校(1) 1005
// 1 2 3 4 上 下 左 右
struct point
{
int val, dir, x, y;
bool operator<(const point& another) const
{
return val > another.val;
}
};
void solve() {
int n, m;
cin >> n >> m;
int t[n + 1][m + 1];
int d[n + 1][m + 1];
int dis[n + 1][m + 1][5];
// 正确初始化 dis 数组
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
for (int k = 1; k <= 4; k++)
{
dis[i][j][k] = INF;
}
}
}
dis[1][1][4] = 0;
bool vis[n + 1][m + 1][5] = {false};
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> t[i][j];
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> d[i][j];
}
}
priority_queue<point> q;
q.push({0, 4, 1, 1});//初始进入时时间为0，方向为右4，坐标为(1,1)
while (!q.empty())
{
auto [val, dir, x, y] = q.top();
q.pop();
if (vis[x][y][dir]) continue;
vis[x][y][dir] = true;
for (int i = 0; i < 4; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
int nextdir;
if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
// 根据 dx 和 dy 判断新方向
if (dx[i] == -1 && dy[i] == 0) nextdir = 3;
if (dx[i] == 1 && dy[i] == 0) nextdir = 1;
if (dx[i] == 0 && dy[i] == 1) nextdir = 4;
if (dx[i] == 0 && dy[i] == -1) nextdir = 2;
if (vis[nx][ny][nextdir]) continue;
int nextw = dis[x][y][dir] + t[x][y];
if (nextdir != dir) nextw += d[x][y];
//类Dijkstra if(dis[v] > dis[u] + w)
if (nextw < dis[nx][ny][nextdir])
{
q.push({nextw, nextdir, nx, ny});
dis[nx][ny][nextdir] = nextw;
}
}
}
int ans = min({dis[n][m][1], dis[n][m][4] + d[n][m],dis[n][m][2] + d[n][m],dis[n][m][3] + d[n][m]}) + t[n][m];
cout << ans << endl;
}
|