| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 475564 | youngyojun | Wall (CEOI14_wall) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define eb emplace_back
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
const bool debug = 0;
const int MAXH = 405;
const int MAXW = 405;
priority_queue<pli, vector<pli>, greater<pli>> PQ;
vector<pii> G[2200022];
ll dp[MAXH*2][MAXW*2]; int dpr[MAXH][MAXW];
bitset<MAXW> chk[MAXH], isB[MAXH], isC[MAXW];
int B[MAXH][MAXW], C[MAXH][MAXW];
int A[MAXH][MAXW];
int H, W;
int f(int y, int x) { return y<<11 | x; }
void updf(int y, int x, ll dst, int dr) {
if(y < 0 || x < 0 || H < y || W < x) return;
if(dp[y][x] <= dst) return;
PQ.push(pli(dst, f(y, x)));
dp[y][x] = dst;
dpr[y][x] = dr;
}
int main() {
ios::sync_with_stdio(false);
cin >> H >> W;
for(int i = 1; i <= H; i++) for(int j = 1; j <= W; j++) cin >> A[i][j];
for(int i = 1; i <= H; i++) for(int j = 0; j <= W; j++) cin >> B[i][j];
for(int i = 0; i <= H; i++) for(int j = 1; j <= W; j++) cin >> C[i][j];
for(int i = 0; i <= H; i++) fill(dp[i], dp[i]+W+1, INFLL);
dp[0][0] = 0; PQ.push(pli(0, 0));
for(int y, x; !PQ.empty();) {
ll dst; tie(dst, y) = PQ.top(); PQ.pop();
x = y & ((1<<11)-1); y >>= 11;
if(dp[y][x] < dst) continue;
updf(y-1, x, dst + B[y][x], 0);
updf(y+1, x, dst + B[y+1][x], 2);
updf(y, x+1, dst + C[y][x+1], 1);
updf(y, x-1, dst + C[y][x], 3);
}
for(int i = 1; i <= H; i++) for(int j = 1; j <= W; j++) if(A[i][j]) {
for(int y = i-1, x = j-1; y || x;) {
if(!dpr[y][x]) {
y++;
isB[y][x] = true;
} else if(1 == dpr[y][x]) {
isC[y][x] = true;
x--;
} else if(2 == dpr[y][x]) {
isB[y][x] = true;
y--;
} else {
x++;
isC[y][x] = true;
}
}
}
if(debug) {
for(int i = 1; i <= H; i++) {
for(int j = 0; j <= W; j++)
printf("%d ", int(isB[i][j]));
puts("");
}
for(int i = 0; i <= H; i++) {
for(int j = 1; j <= W; j++)
printf("%d ", int(isC[i][j]));
puts("");
}
}
for(int i = 1; i <= H; i++) for(int j = 0; j <= W; j++) {
fg(G, f(i*2-1, j*2), f(i*2, j*2), B[i][j]);
fg(G, f(i*2-1, j*2+1), f(i*2, j*2+1), B[i][j]);
}
for(int i = 0; i <= H; i++) for(int j = 1; j <= W; j++) {
fg(G, f(i*2, j*2-1), f(i*2, j*2), C[i][j]);
fg(G, f(i*2+1, j*2-1), f(i*2+1, j*2), C[i][j]);
}
isB[0][0] = isC[0][0] = true;
for(int i = 1; i <= H; i++) for(int j = 1; j <= W; j++) if(A[i][j])
isB[i][j-1] = isB[i][j] = isC[i-1][j] = isC[i][j] = true;
for(int i = 0; i <= H; i++) for(int j = 0; j <= W; j++) {
if(!isB[i][j]) fg(G, f(i*2, j*2), f(i*2, j*2+1), 0);
if(!isC[i][j]) fg(G, f(i*2, j*2), f(i*2+1, j*2), 0);
if(!isB[i+1][j]) fg(G, f(i*2+1, j*2), f(i*2+1, j*2+1), 0);
if(!isC[i][j+1]) fg(G, f(i*2, j*2+1), f(i*2+1, j*2+1), 0);
}
for(int i = 0; i <= H*2+1; i++)
fill(dp[i], dp[i]+W*2+2, INFLL);
dp[0][1] = 0; PQ.push(pli(0, 1));
for(int y, x; !PQ.empty();) {
ll dst; tie(dst, y) = PQ.top(); PQ.pop();
x = y & ((1<<11)-1); y >>= 11;
if(dp[y][x] < dst) continue;
vector<pii> &V = G[f(y, x)];
for(auto &e : V) {
int ny = e.first >> 11, nx = e.first & ((1<<11)-1);
ll ndst = dst + e.second;
if(dp[ny][nx] <= ndst) continue;
dp[ny][nx] = ndst;
PQ.push(pli(ndst, f(ny, nx)));
}
}
cout << dp[1][0] << endl;
return 0;
}