……就是爬管道……

还好内存给的多……

不然就不会做了……

#include<iostream>

#include<map>

#include<string>

#include<cstring>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<queue>

#include<vector>

#include<algorithm>

using namespace std;

const int inf=(1<<31)-1;

int dp[51][51][1<<10];

int road[51][51][51][51];

int key[51][51];

int dx[4]={-1,1,0,0};

int dy[4]={0,0,-1,1};

int n,m,ans;

struct node

{

	int x,y,k,step;

	node(){}

	node(int a,int b,int c,int d){x=a;y=b;k=c;step=d;}

};

bool isin(int x,int y)

{

	return x>=1&&x<=n&&y>=1&&y<=m;

}

void bfs()

{

	int i;

	node now,next;

	queue<node>qq;

	qq.push(node(1,1,key[1][1],0));

	memset(dp,-1,sizeof(dp));

	while(qq.size())

	{

		now=qq.front();

		qq.pop();

		dp[now.x][now.y][now.k]=now.step;

		for(i=0;i<4;i++)

		{

			next=now;

			next.x+=dx[i];

			next.y+=dy[i];

			next.k|=key[next.x][next.y];

			next.step++;

			if(!isin(next.x,next.y))

				continue;

			if(road[now.x][now.y][next.x][next.y]==0)

				continue;

			if(next.x==n&&next.y==m)

			{

				ans=min(ans,next.step);

				continue;

			}

			if(road[now.x][now.y][next.x][next.y]>0)

			{

				if(!((next.k>>road[now.x][now.y][next.x][next.y]-1)&1))

					continue;

			}

			if(dp[next.x][next.y][next.k]!=-1)

			{

				if(next.step>=dp[next.x][next.y][next.k])

					continue;

			}

			qq.push(next);

		}

	}

}

int main()

{

	int p,sx,sy,ex,ey,t,k,x,y;

	while(cin>>n>>m>>p)

	{

		memset(road,-1,sizeof(road));

		cin>>t;

		while(t--)

		{

			cin>>sx>>sy>>ex>>ey>>k;

			road[sx][sy][ex][ey]=k;

			road[ex][ey][sx][sy]=k;

		}

		cin>>t;

		memset(key,0,sizeof(key));

		while(t--)

		{

			cin>>x>>y>>k;

			key[x][y]|=1<<k-1;

		}

		ans=inf;

		bfs();

		if(ans==inf)

			ans=-1;

		cout<<ans<<endl;

	}

}

Maze

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 100000/100000 K (Java/Others)

Total Submission(s): 329    Accepted Submission(s): 125

4 4 9

9

1 2 1 3 2

1 2 2 2 0

2 1 2 2 0

2 1 3 1 0

2 3 3 3 0

2 4 3 4 1

3 2 3 3 0

3 3 4 3 0

4 3 4 4 0

2

2 1 2

4 2 1

14