#include <bits/stdc++.h>
using namespace std;
const int N = 405;
const long long INF = 1e18;
struct State {
long long v;
int x, y, d;
State (long long v, int x, int y, int d) :
v(v), x(x), y(y), d(d) {}
bool operator < (const State& rhs) const {
return d > rhs.d;
}
};
const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};
int n, m;
int cost[4][N][N];
bool a[N][N];
bool vis[N][N];
bool mark[4][N][N];
long long dis[N][N];
long long f[4][N][N];
void dijkstra() {
for (int i = 1; i <= n + 1; ++i) {
for (int j = 1; j <= m + 1; ++j) {
dis[i][j] = INF;
}
}
priority_queue<State> pq;
pq.push(State(dis[1][1] = 0, 1, 1, 0));
while (pq.size()) {
long long v = pq.top().v;
int x = pq.top().x, y = pq.top().y;
pq.pop();
if (v != dis[x][y]) continue;
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 1 || nx > n + 1 || ny < 1 || ny > m + 1) continue;
if (dis[nx][ny] > v + cost[i][x][y]) {
dis[nx][ny] = v + cost[i][x][y];
pq.push(State(dis[nx][ny], nx, ny, 0));
}
}
}
}
void rec(int x, int y) {
if (x == 1 && y == 1 || vis[x][y]) return;
vis[x][y] = 1;
for (int i = 0; i < 4; ++i) {
int nx = x - dx[i], ny = y - dy[i];
if (nx < 1 || nx > n + 1 || ny < 1 || ny > m + 1) continue;
if (dis[nx][ny] + cost[i][nx][ny] == dis[x][y]) {
mark[i ^ 1][x][y] = mark[i][nx][ny] = 1, rec(nx, ny); return;
}
}
}
void solve() {
for (int i = 1; i <= n + 1; ++i) {
for (int j = 1; j <= m + 1; ++j) {
for (int k = 0; k < 4; ++k) {
f[k][i][j] = INF;
}
}
}
priority_queue<State> pq;
pq.push(State(f[1][1][2] = cost[1][1][1], 1, 2, 1));
while (pq.size()) {
long long v = pq.top().v;
int x = pq.top().x, y = pq.top().y, d = pq.top().d;
pq.pop();
if (v != f[d][x][y]) continue;
if ( !(d == 0 && mark[3][x][y] || d == 1 || d == 3 && (mark[1][x][y] || mark[3][x][y]) || y == 1) ) {
if (f[0][x][y - 1] > v + cost[0][x][y]) {
f[0][x][y - 1] = v + cost[0][x][y];
pq.push(State(f[0][x][y - 1], x, y - 1, 0));
}
}
if ( !(d == 0 || d == 1 && mark[2][x][y] || d == 2 && (mark[0][x][y] || mark[2][x][y]) || y == m + 1) ) {
if (f[1][x][y + 1] > v + cost[1][x][y]) {
f[1][x][y + 1] = v + cost[1][x][y];
pq.push(State(f[1][x][y + 1], x, y + 1, 1));
}
}
if ( !(d == 0 && (mark[0][x][y] || mark[3][x][y]) || d == 2 && mark[0][x][y] || d == 3 || x == 1) ) {
if (f[2][x - 1][y] > v + cost[2][x][y]) {
f[2][x - 1][y] = v + cost[2][x][y];
pq.push(State(f[2][x - 1][y], x - 1, y, 2));
}
}
if ( !(d == 1 && (mark[1][x][y] || mark[2][x][y]) || d == 2 || d == 3 && mark[1][x][y] || x == n + 1) ) {
if (f[3][x + 1][y] > v + cost[3][x][y]) {
f[3][x + 1][y] = v + cost[3][x][y];
pq.push(State(f[3][x + 1][y], x + 1, y, 3));
}
}
// if (d == 0) {
// for (auto i : G[x][y]) {
// if (i.d == 1) continue;
// if (i.d == 0 && mark[3][x][y]) continue;
// if (i.d == 2 && (mark[0][x][y] || mark[3][x][y])) continue;
// if (f[i.d][i.x][i.y] > v + i.w) {
// f[i.d][i.x][i.y] = v + i.w;
// pq.push(State(v + i.w, i.x, i.y, i.d));
// }
// }
// }
// if (d == 1) {
// for (auto i : G[x][y]) {
// if (i.d == 0) continue;
// if (i.d == 1 && mark[2][x][y]) continue;
// if (i.d == 3 && (mark[1][x][y] || mark[2][x][y])) continue;
// if (f[i.d][i.x][i.y] > v + i.w) {
// f[i.d][i.x][i.y] = v + i.w;
// pq.push(State(v + i.w, i.x, i.y, i.d));
// }
// }
// }
// if (d == 2) {
// for (auto i : G[x][y]) {
// if (i.d == 3) continue;
// if (i.d == 2 && mark[0][x][y]) continue;
// if (i.d == 1 && (mark[0][x][y] || mark[2][x][y])) continue;
// if (f[i.d][i.x][i.y] > v + i.w) {
// f[i.d][i.x][i.y] = v + i.w;
// pq.push(State(v + i.w, i.x, i.y, i.d));
// }
// }
// }
// if (d == 3) {
// for (auto i : G[x][y]) {
// if (i.d == 2) continue;
// if (i.d == 3 && mark[1][x][y]) continue;
// if (i.d == 0 && (mark[1][x][y] || mark[3][x][y])) continue;
// if (f[i.d][i.x][i.y] > v + i.w) {
// f[i.d][i.x][i.y] = v + i.w;
// pq.push(State(v + i.w, i.x, i.y, i.d));
// }
// }
// }
}
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
cin >> a[i][j];
if (a[i][j]) {
mark[0][i][j + 1] = mark[0][i + 1][j + 1] = 1;
mark[1][i][j] = mark[1][i + 1][j] = 1;
mark[2][i + 1][j] = mark[2][i + 1][j + 1] = 1;
mark[3][i][j] = mark[3][i][j + 1] = 1;
}
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m + 1; ++j) {
int w; cin >> w;
cost[3][i][j] = cost[2][i + 1][j] = w;
}
}
for (int i = 1; i <= n + 1; ++i) {
for (int j = 1; j <= m; ++j) {
int w; cin >> w;
cost[1][i][j] = cost[0][i][j + 1] = w;
}
}
dijkstra();
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (a[i][j]) rec(i, j);
}
}
// for (int i = 1; i <= n + 1; ++i) {
// for (int j = 1; j <= m + 1; ++j) {
// for (int k = 1; k < 4; k += 2) {
// if (mark[k][i][j]) {
// cout << i << ' ' << j << ' ' << k << '\n';
// }
// }
// }
// }
solve();
cout << f[2][1][1];
}
Compilation message
wall.cpp: In function 'void rec(int, int)':
wall.cpp:56:13: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if (x == 1 && y == 1 || vis[x][y]) return;
~~~~~~~^~~~~~~~~
wall.cpp: In function 'void solve()':
wall.cpp:83:17: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if ( !(d == 0 && mark[3][x][y] || d == 1 || d == 3 && (mark[1][x][y] || mark[3][x][y]) || y == 1) ) {
~~~~~~~^~~~~~~~~~~~~~~~
wall.cpp:83:54: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if ( !(d == 0 && mark[3][x][y] || d == 1 || d == 3 && (mark[1][x][y] || mark[3][x][y]) || y == 1) ) {
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:90:27: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if ( !(d == 0 || d == 1 && mark[2][x][y] || d == 2 && (mark[0][x][y] || mark[2][x][y]) || y == m + 1) ) {
~~~~~~~^~~~~~~~~~~~~~~~
wall.cpp:90:54: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if ( !(d == 0 || d == 1 && mark[2][x][y] || d == 2 && (mark[0][x][y] || mark[2][x][y]) || y == m + 1) ) {
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:97:17: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if ( !(d == 0 && (mark[0][x][y] || mark[3][x][y]) || d == 2 && mark[0][x][y] || d == 3 || x == 1) ) {
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:104:17: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if ( !(d == 1 && (mark[1][x][y] || mark[2][x][y]) || d == 2 || d == 3 && mark[1][x][y] || x == n + 1) ) {
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:104:73: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if ( !(d == 1 && (mark[1][x][y] || mark[2][x][y]) || d == 2 || d == 3 && mark[1][x][y] || x == n + 1) ) {
~~~~~~~^~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
632 KB |
Output is correct |
| 2 |
Correct |
3 ms |
744 KB |
Output is correct |
| 3 |
Correct |
3 ms |
744 KB |
Output is correct |
| 4 |
Correct |
2 ms |
744 KB |
Output is correct |
| 5 |
Correct |
4 ms |
876 KB |
Output is correct |
| 6 |
Correct |
27 ms |
1912 KB |
Output is correct |
| 7 |
Correct |
20 ms |
1912 KB |
Output is correct |
| 8 |
Correct |
23 ms |
1912 KB |
Output is correct |
| 9 |
Correct |
30 ms |
1912 KB |
Output is correct |
| 10 |
Correct |
48 ms |
1912 KB |
Output is correct |
| 11 |
Correct |
31 ms |
2104 KB |
Output is correct |
| 12 |
Correct |
64 ms |
2104 KB |
Output is correct |
| 13 |
Correct |
96 ms |
2164 KB |
Output is correct |
| 14 |
Correct |
112 ms |
2164 KB |
Output is correct |
| 15 |
Correct |
101 ms |
2288 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
38 ms |
2288 KB |
Output is correct |
| 2 |
Correct |
122 ms |
2552 KB |
Output is correct |
| 3 |
Correct |
84 ms |
3316 KB |
Output is correct |
| 4 |
Correct |
44 ms |
3316 KB |
Output is correct |
| 5 |
Correct |
106 ms |
3316 KB |
Output is correct |
| 6 |
Correct |
222 ms |
3316 KB |
Output is correct |
| 7 |
Correct |
91 ms |
3316 KB |
Output is correct |
| 8 |
Correct |
94 ms |
3316 KB |
Output is correct |
| 9 |
Correct |
81 ms |
3316 KB |
Output is correct |
| 10 |
Correct |
43 ms |
3316 KB |
Output is correct |
| 11 |
Correct |
60 ms |
3316 KB |
Output is correct |
| 12 |
Correct |
176 ms |
3316 KB |
Output is correct |
| 13 |
Correct |
45 ms |
3316 KB |
Output is correct |
| 14 |
Correct |
110 ms |
3316 KB |
Output is correct |
| 15 |
Correct |
86 ms |
3316 KB |
Output is correct |
| 16 |
Correct |
59 ms |
3316 KB |
Output is correct |
| 17 |
Correct |
77 ms |
3316 KB |
Output is correct |
| 18 |
Correct |
166 ms |
3380 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2076 ms |
6128 KB |
Time limit exceeded |
| 2 |
Execution timed out |
2083 ms |
6128 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2080 ms |
6128 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2048 ms |
6128 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2058 ms |
7396 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2065 ms |
7396 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2061 ms |
10552 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2085 ms |
10552 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2061 ms |
10552 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2075 ms |
10552 KB |
Time limit exceeded |
| 11 |
Execution timed out |
2073 ms |
10552 KB |
Time limit exceeded |
| 12 |
Execution timed out |
2066 ms |
10552 KB |
Time limit exceeded |
| 13 |
Execution timed out |
2072 ms |
10552 KB |
Time limit exceeded |
| 14 |
Execution timed out |
2086 ms |
11364 KB |
Time limit exceeded |
| 15 |
Execution timed out |
2070 ms |
11364 KB |
Time limit exceeded |
| 16 |
Execution timed out |
2076 ms |
11364 KB |
Time limit exceeded |
| 17 |
Execution timed out |
2082 ms |
11364 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2073 ms |
11364 KB |
Time limit exceeded |
| 19 |
Execution timed out |
2076 ms |
11364 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2066 ms |
11364 KB |
Time limit exceeded |
