相关链接
题目传送门：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_solutionCode
#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;
}
Hi there! Quick question that’s entirely off topic.
Do you know how to make your site mobile friendly? My weblog
looks weird when browsing from my iphone4. I’m trying to find a
theme or plugin that might be able to correct this problem.
If you have any recommendations, please share. Cheers!
What i do not understood is if truth be told how you are now not actually
much more well-appreciated than you might be now.
You are so intelligent. You already know therefore significantly in relation to this subject, made me
in my opinion imagine it from a lot of numerous angles.
Its like men and women are not interested except it’s something to do
with Woman gaga! Your personal stuffs outstanding. All the time care for it
up!
Hey There. I found your blog using msn. This is a really well written article.
I will be sure to bookmark it and come back to read more of your useful info.
Thanks for the post. I’ll certainly return.
This is very interesting, You’re a very skilled blogger.
I’ve joined your rss feed and look forward to in the hunt for
more of your magnificent post. Additionally, I’ve
shared your web site in my social networks
We are a group of volunteers and opening a brand
new scheme in our community. Your web site offered us with helpful information to work on. You have
performed a formidable task and our whole group might be thankful
to you.
Hello, I want to subscribe for this website to take most recent updates, therefore where can i do it please assist.
Hello to all, because I am truly keen of reading this web site’s post to be updated
daily. It consists of fastidious material.
I’m not that much of a internet reader to be honest but your blogs really nice, keep
it up! I’ll go ahead and bookmark your site to
come back later. All the best
Hey there! This post could not be written any better!
Reading this post reminds me of my good old room mate!
He always kept talking about this. I will forward this write-up to him.
Fairly certain he will have a good read. Many thanks for sharing!
Thanks for the marvelous posting! I certainly enjoyed reading it, you may be a great author.
I will make sure to bookmark your blog and will often come back someday.
I want to encourage you to continue your great work, have a nice day!
Good answers in return of this issue with genuine arguments
and telling the whole thing concerning that.
Hey there! This post could not be written any better!
Reading through this post reminds me of my previous room mate!
He always kept chatting about this. I will forward this write-up to him.
Fairly certain he will have a good read. Thank you for sharing!
I enjoy what you guys tend to be up too. Such clever work and coverage!
Keep up the good works guys I’ve incorporated you guys to my
personal blogroll.
Great article, exactly what I was looking for.
Hello! Would you mind if I share your blog with my myspace group? There’s a lot of people that I think would really enjoy your content. Please let me know. Thanks
Pretty! This was an incredibly wonderful article. Many thanks for providing
these details.
It’s wonderful that you are getting ideas from this piece of writing
as well as from our discussion made here.
Thanks a lot for sharing this with all of us you really
realize what you’re speaking about! Bookmarked.
Please additionally talk over with my web site =).
We will have a hyperlink change contract between us
I really like it whenever people get together and share opinions.
Great site, keep it up!
Wonderful web site. A lot of useful information here. I’m sending it to some
pals ans additionally sharing in delicious. And naturally, thanks on your sweat!
Superb website you have here but I was wanting to
know if you knew of any discussion boards that cover the same topics
discussed here? I’d really love to be a part of community where I
can get feed-back from other experienced people that
share the same interest. If you have any recommendations, please let me know.
Kudos!
I really like what you guys are usually up too. Such clever
work and exposure! Keep up the very good works guys I’ve incorporated you guys
to our blogroll.
Hi there, after reading this amazing piece of writing i am too glad to share my experience
here with colleagues.
Hey there! I just wanted to ask if you ever have any
problems with hackers? My last blog (wordpress) was hacked and I ended up losing a few months of
hard work due to no backup. Do you have any methods to protect against hackers?
Asking questions are really good thing if you are not understanding anything completely, however this piece of writing presents good understanding even.
It’s an awesome post in favor of all the internet
people; they will take benefit from it I am sure.
Definitely, what a magnificent site and illuminating posts, I surely will bookmark your site.Have an awsome day!