和网络流有半毛钱关系么......
可以发现 $n,m,p$ 都特别小, 那么考虑状压, 每一个状态表示位置以及钥匙的拥有情况, 然后每次因为只能走一步, 所以可以用 bfs 求出最优解
然后是某大佬说的注意点: 每个点可以有很多钥匙, 而且初始点也有可能有钥匙
- //minamoto
- #include<iostream>
- #include<cstdio>
- #include<queue>
- using namespace std;
- #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
- char buf[1<<21],*p1=buf,*p2=buf;
- inline int read(){
- #define num ch-'0'
- char ch;bool flag=0;int res;
- while(!isdigit(ch=getc()))
- (ch=='-')&&(flag=true);
- for(res=num;isdigit(ch=getc());res=res*10+num);
- (flag)&&(res=-res);
- #undef num
- return res;
- }
- const int N=11;
- int vis[N][N][(1<<N)],map[N][N][N][N],pas[N][N][N],num[N][N];
- struct node{
- int x,y,step,now;
- node(){}
- node(int x,int y,int step,int now):x(x),y(y),step(step),now(now){}
- };
- queue<node> q;
- int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
- int n,m,p,k;
- int bfs(){
- int now=0;
- for(int i=1;i<=num[1][1];++i)
- now|=(1<<(pas[1][1][i]-1));
- vis[1][1][now]=1;
- q.push(node(1,1,0,now));
- while(!q.empty()){
- node u=q.front();q.pop();
- if(u.x==n&&u.y==m) return u.step;
- for(int i=0;i<4;++i){
- int xx=u.x+dx[i],yy=u.y+dy[i],t;
- if(xx<1||xx>n||yy<1||yy>m) continue;
- if(map[u.x][u.y][xx][yy]==-1) continue;
- if((t=map[u.x][u.y][xx][yy]))
- if(!(u.now&(1<<(t-1)))) continue;
- int nowx=u.now;
- for(int j=1;j<=num[xx][yy];++j)
- nowx|=(1<<(pas[xx][yy][j]-1));
- if(vis[xx][yy][nowx]) continue;
- vis[xx][yy][nowx]=1;
- q.push(node(xx,yy,u.step+1,nowx));
- }
- }
- return -1;
- }
- int main(){
- n=read(),m=read(),p=read(),k=read();
- for(int i=1;i<=k;++i){
- int x1,x2,y1,y2,g;
- x1=read(),y1=read(),x2=read(),y2=read(),g=read();
- if(g==0) map[x1][y1][x2][y2]=map[x2][y2][x1][y1]=-1;
- else map[x1][y1][x2][y2]=map[x2][y2][x1][y1]=g;
- }
- int s=read();
- for(int i=1;i<=s;++i){
- int x=read(),y=read(),p=read();
- pas[x][y][++num[x][y]]=p;
- }
- printf("%d\n",bfs());
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2733633.html