很好奇三个关键词怎么放在一起的QAQ
by qian_shang @ 2019-11-05 17:04:50
太弱了，一直留级。
by desize @ 2019-11-05 17:06:36
17岁高三吗
不太科学
by OvOAuto @ 2019-11-05 17:06:41
~~不是暴力BFS就能过吗QAQ~~
by 南欺姬 @ 2019-11-05 17:15:55
加了点注释。
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,p,k,enge[12][12][12][12],pd[12][12][12][12],v[32770][12][12];
long long d[32770][12][12];
int xx[4]={0,0,-1,1},yy[4]={-1,1,0,0};
int s,ys[12][12];
struct dsz{
int x,y,zt;
long long sj;
};
bool operator <(const dsz &a,const dsz &b)
{
return a.sj<b.sj;
}
priority_queue<dsz> q;
int main()
{
memset(ys,0,sizeof(ys));
memset(pd,0x3f3f3f3f,sizeof(pd));
memset(enge,0x3f3f3f3f,sizeof(enge));//初始所有道路不能行走
scanf("%d%d%d%d",&n,&m,&p,&k);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int k=0;k<4;k++)
if(i+xx[k]>=1&&i+xx[k]<=n
&&j+yy[k]>=1&&j+yy[k]<=m)
enge[i][j][i+xx[k]][j+yy[k]]=1;//相邻点可走
for(int i=1;i<=k;i++)
{
int x1,x2,y1,y2,g;
scanf("%d%d%d%d%d",&x1,&x2,&y1,&y2,&g);
if(g==0)
{
enge[x1][x2][y1][y2]=1061109567;
enge[y1][y2][x1][x2]=1061109567;//墙不能走
}
else
{
pd[x1][x2][y1][y2]=g-1;
pd[y1][y2][x1][x2]=g-1;//存储门的位置
}
}
scanf("%d",&s);
for(int i=0;i<s;i++)
{
int x,y,q;
scanf("%d%d%d",&x,&y,&q);
ys[x][y]|=(1<<(q-1));//存储钥匙的位置
}
memset(d,0x3F3F3F3F,sizeof(d));
memset(v,0,sizeof(v));
d[ys[1][1]][1][1]=0;//起点如果有钥匙就存储
dsz qd={1,1,ys[1][1],0};
q.push(qd);
while(!q.empty())
{
dsz x=q.top();
q.pop();
if(v[x.zt][x.x][x.y])
continue;
v[x.zt][x.x][x.y]=1;
for(int k=0;k<4;k++)
{
if(x.x+xx[k]<1||x.x+xx[k]>n
||x.y+yy[k]<1||x.y+yy[k]>m//越界判断
||enge[x.x][x.y][x.x+xx[k]][x.y+yy[k]]==1061109567//墙不能走
||enge[x.x][x.y][x.x+xx[k]][x.y+yy[k]]==1//无门或有钥匙可走
&&pd[x.x][x.y][x.x+xx[k]][x.y+yy[k]]!=1061109567
&&!((x.zt>>pd[x.x][x.y][x.x+xx[k]][x.y+yy[k]])&1))
continue;
int xy=x.x+xx[k],yx=x.y+yy[k];
int op=x.zt|ys[xy][yx];
if(d[op][xy][yx]>d[x.zt][x.x][x.y]+1)
{
d[op][xy][yx]=d[x.zt][x.x][x.y]+1;
if(xy==n&&yx==m)
{
printf("%lld",d[op][xy][yx]);//输出
return 0;
}
dsz y={xy,yx,op,d[op][xy][yx]};
q.push(y);
}
}
}
printf("-1");
return 0;
}
```
by desize @ 2019-11-14 19:37:57
你这个敌劫的运算符重载怎么不是很一样……
by _MRCMRC_ @ 2019-11-14 19:48:16
并且这题最短路方法貌似会更麻烦吧
by _MRCMRC_ @ 2019-11-14 19:48:39
by desize @ 2019-11-14 19:56:55
by desize @ 2019-11-14 19:57:27
@[北冥、流风](/user/112742) 感谢大佬，是我sb了，运算符重载打反了。
by desize @ 2019-11-14 19:58:42