| 记录编号 |
93339 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[WC 1999]迷宫改造 |
最终得分 |
100 |
| 用户昵称 |
 cstdio |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.018 s |
| 提交时间 |
2014-03-25 20:10:29 |
内存使用 |
0.98 MiB |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int SIZEn=30,SIZEN=10800+10,INF=0x7fffffff/2;
//本题下标从0开始
int n,m,K;//N行M列K个墙
bool around[SIZEn][SIZEn][5]={0};
//上下左右分别是0123
//x行y列
int srcx[5]={0},srcy[5]={0},desx[5]={0},desy[5]={0};//三个人的起点和终点
int P;
int dx[5]={-1,1,0,0},dy[5]={0,0,-1,1};
void SPFA(vector<pair<int,int> > c[SIZEN],int N,int S,int f[SIZEN]){//图中顶点0~N-1,邻接表为c,以S出发,结果存于f
queue<int> Q;
bool inq[SIZEN]={0};
for(int i=0;i<N;i++) f[i]=INF;
f[S]=0,inq[S]=true,Q.push(S);
while(!Q.empty()){
int x=Q.front();Q.pop();inq[x]=false;
for(int i=0;i<c[x].size();i++){
int u=c[x][i].first;
if(f[x]+c[x][i].second<f[u]){
f[u]=f[x]+c[x][i].second;
if(!inq[u]){
inq[u]=true;
Q.push(u);
}
}
}
}
}
vector<pair<int,int> > monose[SIZEN],mononw[SIZEN];//单层图,只向东南和只向西北
vector<pair<int,int> > layer[SIZEN];//分层图
int distsrc[3][SIZEN]={0},distdes[3][SIZEN]={0};//从每个人起点,终点出发的最短路
int bypasslen[3]={0};//自己单独走的长度
void printstate(int s){//调试接口,输出点代表的状态
int y=s%m;s/=m;
int x=s%n;s/=n;
int e2=s%3;s/=3;
int e1=s%3;s/=3;
int e0=s;
cout<<"("<<e0<<e1<<e2<<" "<<x<<" "<<y<<")";
}
int hash(int e0,int e1,int e2,int x,int y){
int s=e0*9+e1*3+e2;
return (s*n+x)*m+y;
}
int hash(int x,int y){return x*m+y;}//不考虑进出状态的hash
void makeartery(int e0,int e1,int e2){//建立分层图
//这函数太TM丑了!!!!!!!!!
for(int i=0;i<27*m*n;i++) layer[i].clear();
for(int et0=0;et0<=e0*2;et0++){
for(int et1=0;et1<=e1*2;et1++){
for(int et2=0;et2<=e2*2;et2++){
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
for(int d=1;d<=3;d+=2){
int nx=i+dx[d],ny=j+dy[d];
if(nx<0||nx>n-1||ny<0||ny>m-1) continue;
int w;
if(et0==1||et1==1||et2==1) w=around[i][j][d];//如果有人在干路上那么计入权值
else w=0;//否则不计入
layer[hash(et0,et1,et2,i,j)].push_back(make_pair(hash(et0,et1,et2,nx,ny),w));//这是基本图
}
}
}
}
}
}
int s1,s2;
if(e0){//它存在进入/离开的可能性
for(int et1=0;et1<=e1*2;et1++){
for(int et2=0;et2<=e2*2;et2++){
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
s1=hash(0,et1,et2,i,j),s2=hash(1,et1,et2,i,j);
layer[s1].push_back(make_pair(s2,distsrc[0][hash(i,j)]));//进入干道
s1=hash(1,et1,et2,i,j),s2=hash(2,et1,et2,i,j);
layer[s1].push_back(make_pair(s2,distdes[0][hash(i,j)]));//离开干道
}
}
}
}
}
if(e1){
for(int et0=0;et0<=e0*2;et0++){
for(int et2=0;et2<=e2*2;et2++){
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
s1=hash(et0,0,et2,i,j),s2=hash(et0,1,et2,i,j);
layer[s1].push_back(make_pair(s2,distsrc[1][hash(i,j)]));
s1=hash(et0,1,et2,i,j),s2=hash(et0,2,et2,i,j);
layer[s1].push_back(make_pair(s2,distdes[1][hash(i,j)]));
}
}
}
}
}
if(e2){
for(int et0=0;et0<=e0*2;et0++){
for(int et1=0;et1<=e1*2;et1++){
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
s1=hash(et0,et1,0,i,j),s2=hash(et0,et1,1,i,j);
layer[s1].push_back(make_pair(s2,distsrc[2][hash(i,j)]));
s1=hash(et0,et1,1,i,j),s2=hash(et0,et1,2,i,j);
layer[s1].push_back(make_pair(s2,distdes[2][hash(i,j)]));
}
}
}
}
}
}
int f[SIZEN]={0};
int test(int e0,int e1,int e2){
makeartery(e0,e1,e2);
int ans;
SPFA(layer,27*m*n,0,f);
ans=f[hash(e0*2,e1*2,e2*2,n-1,m-1)];
if(!e0) ans+=bypasslen[0];
if(!e1) ans+=bypasslen[1];
if(!e2) ans+=bypasslen[2];
return ans;
}
void work(void){
int ans=INF;
for(int i=0;i<=1;i++){
for(int j=0;j<=1;j++){
for(int k=0;k<=1;k++) ans=min(ans,test(i,j,k));
}
}
printf("%d\n",ans);
}
void getbypass(void){
for(int i=0;i<3;i++) SPFA(monose,n*m,hash(srcx[i],srcy[i]),distsrc[i]);
for(int i=0;i<3;i++) SPFA(mononw,n*m,hash(desx[i],desy[i]),distdes[i]);
for(int i=0;i<3;i++) bypasslen[i]=distsrc[i][hash(desx[i],desy[i])];
}
void makemonograph(void){
int s1,s2;
for(int i=0;i<n;i++){//东和南
for(int j=0;j<m;j++){
s1=hash(i,j);
for(int d=1;d<=3;d+=2){
int nx=i+dx[d],ny=j+dy[d];
if(nx<0||nx>n-1||ny<0||ny>m-1) continue;
s2=hash(nx,ny);
monose[s1].push_back(make_pair(s2,around[i][j][d]));
}
}
}
for(int i=0;i<n;i++){//西和北
for(int j=0;j<m;j++){
s1=hash(i,j);
for(int d=0;d<=2;d+=2){
int nx=i+dx[d],ny=j+dy[d];
if(nx<0||nx>n-1||ny<0||ny>m-1) continue;
s2=hash(nx,ny);
mononw[s1].push_back(make_pair(s2,around[i][j][d]));
}
}
}
}
int checkdir(int x1,int y1,int x2,int y2){//2在1的什么方位
if(x2<x1) return 0;
if(x2>x1) return 1;
if(y2<y1) return 2;
if(y2>y1) return 3;
return -1;
}
void read(void){
scanf("%d%d%d",&n,&m,&K);
int x1,y1,x2,y2;
memset(around,1,sizeof(around));
for(int i=0;i<K;i++){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
x1--,y1--,x2--,y2--;
around[x1][y1][checkdir(x1,y1,x2,y2)]=0;
around[x2][y2][checkdir(x2,y2,x1,y1)]=0;
}
for(int i=0;i<m;i++) around[0][i][0]=1,around[n-1][i][1]=1;
for(int i=0;i<n;i++) around[i][0][2]=1,around[i][m-1][3]=1;//四周围一圈
scanf("%d",&P);
for(int i=0;i<P;i++) scanf("%d%d%d%d",&srcx[i],&srcy[i],&desx[i],&desy[i]),srcx[i]--,srcy[i]--,desx[i]--,desy[i]--;
for(int i=P;i<3;i++) srcx[i]=srcx[P-1],srcy[i]=srcy[P-1],desx[i]=desx[P-1],desy[i]=desy[P-1];
P=3;
}
int main(){
freopen("rebuildmaze.in","r",stdin);
freopen("rebuildmaze.out","w",stdout);
read();
makemonograph();
getbypass();
work();
return 0;
}