相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4356
神犇题解Ⅰ:http://www.cnblogs.com/clrs97/p/5196611.html
神犇题解Ⅱ:http://www.cnblogs.com/New-Godess/p/4424149.html
解题报告
bzoj_4356_solution
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int L = 400 + 9;
const int N = L * L * 4;
const int M = N * 4;
const LL INF = 1e17;
int n,m,tot,E,head[N],nxt[M],to[M],cost[M];
int cx[L][L],cy[L][L],intree[L][L];
int dx[]={0,1,0,-1,0},dy[]={0,0,1,0,-1};
bool del[L][L][4],vis[L][L],done[N],bst[L][L][4];
LL dis[N];
priority_queue<pair<LL, int> > que;
inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}
inline void Add_Edge(int u, int v, int c) {
to[++E] = v; nxt[E] = head[u]; head[u] = E; cost[E] = c;
to[++E] = u; nxt[E] = head[v]; head[v] = E; cost[E] = c;
}
inline int id(int x, int y, int t = 0) {
if (!t) return x + (y - 1) * (n + 1);
else return (x - 1 + (y - 1) * (n + 1) << 2) + t;
}
inline void Dijkstra(int s) {
memset(done, 0, sizeof(done));
fill(dis, dis+N, INF); dis[s] = 0;
que.push(make_pair(0, s));
for (int w;!que.empty();) {
w = que.top().second; que.pop();
if (done[w]) continue;
done[w] = 1;
for (int i=head[w];i;i=nxt[i]) {
if (dis[to[i]] > dis[w] + cost[i]) {
dis[to[i]] = dis[w] + cost[i];
que.push(make_pair(-dis[to[i]], to[i]));
}
}
}
}
bool mark(int x, int y, int f) {
if (intree[x][y]) return ~intree[x][y]?1:0;
bool tag = vis[x][y];
for (int w=id(x,y),i=head[w];i;i=nxt[i]) {
if (dis[w] + cost[i] == dis[to[i]] && to[i] != f) {
for (int j=1,nx,ny;j<=4;j++) {
nx = x + dx[j]; ny = y + dy[j];
if (id(nx, ny) == to[i]) {
if (mark(nx, ny, w)) {
bst[x][y][j] = tag = 1;
bst[nx][ny][j+2>4?j-2:j+2] = 1;
}
break;
}
}
}
}
intree[x][y] = tag?1:-1;
return tag;
}
int main() {
m = read(); n = read();
del[1][1][2] = del[1][1][4] = 1;
for (int j=1;j<=m;j++) {
for (int i=1;i<=n;i++) {
if (read()) {
vis[i][j] = 1;
del[i][j][4] = 1;
del[i+1][j][3] = 1;
del[i][j+1][1] = 1;
del[i+1][j+1][2] = 1;
}
}
}
for (int j=1,tmp;j<=m;j++) {
for (int i=1;i<=n+1;i++) {
cy[i][j] = tmp = read();
Add_Edge(id(i, j), id(i, j+1), tmp);
}
}
for (int j=1,tmp;j<=m+1;j++) {
for (int i=1;i<=n;i++) {
cx[i][j] = tmp = read();
Add_Edge(id(i, j), id(i+1, j), tmp);
}
}
Dijkstra(id(1,1));
mark(1, 1, id(1, 1));
E = 0; memset(head,0,sizeof(head));
for (int j=1;j<=m+1;j++) {
for (int i=1;i<=n+1;i++) {
if (!del[i][j][1]) {
if (!del[i][j][4] && !bst[i][j][1]) Add_Edge(id(i, j, 1), id(i, j, 4), 0);
if (i <= n && !del[i+1][j][2]) Add_Edge(id(i, j, 1), id(i+1, j, 2), cx[i][j]);
}
if (!del[i][j][2]) {
if (!del[i][j][1] && !bst[i][j][4]) Add_Edge(id(i, j, 2), id(i, j, 1), 0);
if (!del[i][j][3] && !bst[i][j][3]) Add_Edge(id(i, j, 2), id(i, j, 3), 0);
}
if (!del[i][j][3]) {
if (!del[i][j][4] && !bst[i][j][2]) Add_Edge(id(i, j, 3), id(i, j, 4), 0);
if (j <= m && !del[i][j+1][2]) Add_Edge(id(i, j, 3), id(i, j+1, 2), cy[i][j]);
}
if (!del[i][j][4]) {
if (i <= n && !del[i+1][j][3]) Add_Edge(id(i, j, 4), id(i+1, j, 3), cx[i][j]);
if (j <= m && !del[i][j+1][1]) Add_Edge(id(i, j, 4), id(i, j+1, 1), cy[i][j]);
}
}
}
Dijkstra(id(1,1,3));
printf("%lld\n",dis[id(1,1,1)]);
return 0;
}