链接：http://acm.hdu.edu.cn/showproblem.php?pid=4845
分析：其实可以直接bfs或者ida*的。。就是无解的时候不太好搞。。
首先钥匙数<=10，可以状压一下，然后共不超过2^10总状态，每种状态下搞一个图，把不同状态的图通过有钥匙的点连接起来，把终点全部连起来，然后搞一下最短路径即可。注意hdu上的多组数据。。因为这个wa了好几发。。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<vector> 5 #include<stack> 6 #include<queue> 7 using namespace std; 8 const int maxn=16,maxstatus=1<<10,inf=1e9; 9 int n,m,p,k; 10 void Swap(int &a,int &b){int t=a;a=b;b=t;} 11 bool wall[maxn*maxn][maxn*maxn]; 12 int dis[maxstatus*maxn*maxn+maxn*maxn+1]; 13 bool inq[maxstatus*maxn*maxn+maxn*maxn+1]; 14 struct door{ 15 int x,y; 16 door(int x,int y){this->x=x;this->y=y;} 17 }; 18 struct Edge{ 19 int to,dis; 20 Edge (int to,int dis){ 21 this->to=to;this->dis=dis; 22 } 23 }; 24 vector<Edge> G[maxstatus*maxn*maxn+maxn*maxn+1]; 25 vector<door> d[15]; 26 void add(int s,int t,int dis){ 27 G[s].push_back(Edge(t,dis)); 28 G[t].push_back(Edge(s,dis)); 29 } 30 void build(){ 31 for(int status=0;status<(1<<p);status++){ 32 int delta=status*maxn*maxn; 33 for(int i=1;i<=n;i++){ 34 for(int j=1;j<=m;j++){ 35 int x=maxn*i+j,y; 36 if(j<m){ 37 y=maxn*i+j+1; 38 if(!wall[x][y])add(delta+x,delta+y,1); 39 } 40 if(i<n){ 41 y=maxn*(i+1)+j; 42 if(!wall[x][y])add(delta+x,delta+y,1); 43 } 44 } 45 } 46 for(int i=1;i<=p;i++){ 47 if(((1<<(i-1))&status)==0)continue; 48 for(int j=0;j<d[i].size();j++){ 49 add(delta+d[i][j].x,delta+d[i][j].y,1); 50 } 51 } 52 } 53 for(int i=0;i<(1<<p)-1;i++){ 54 //add(i*maxn*maxn+maxn+1,(i+1)*maxn*maxn+maxn+1,0); 55 add(i*maxn*maxn+n*maxn+m,(i+1)*maxn*maxn+n*maxn+m,0); 56 } 57 } 58 int spfa(){ 59 int s=maxn+1,t=maxn*n+m; 60 for(int i=0;i<=maxstatus*maxn*maxn+maxn*maxn;i++)dis[i]=inf; 61 memset(inq,0,sizeof(inq)); 62 queue<int> Q; 63 Q.push(s); 64 inq[s]=true; 65 dis[s]=0; 66 while(!Q.empty()){ 67 int x=Q.front();Q.pop(); 68 inq[x]=false; 69 for(int i=0;i<G[x].size();i++){ 70 int to=G[x][i].to; 71 if(dis[to]>dis[x]+G[x][i].dis){ 72 dis[to]=dis[x]+G[x][i].dis; 73 if(!inq[to]){ 74 Q.push(to);inq[to]; 75 } 76 } 77 } 78 } 79 if(dis[t]==inf)return -1; 80 return dis[t]; 81 } 82 int main(){ 83 // freopen("e:\in.txt","r",stdin); 84 while(scanf("%d%d%d",&n,&m,&p)!=EOF){ 85 for(int i=0;i<15;i++)d[i].clear(); 86 for(int i=0;i<=(1<<p)*maxn*maxn+maxn*maxn;i++)G[i].clear(); 87 memset(wall,0,sizeof(wall)); 88 int k,x1,y1,x2,y2,g,s; 89 scanf("%d",&k); 90 for(int i=0;i<k;i++){ 91 scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&g); 92 int u=x1*maxn+y1,t=x2*maxn+y2; 93 if(u>t)Swap(u,t); 94 wall[u][t]=true; 95 if(g){ 96 d[g].push_back(door(u,t)); 97 } 98 } 99 scanf("%d",&s); 100 while(s--){ 101 scanf("%d%d%d",&x1,&y1,&g); 102 int t=1<<(g-1); 103 for(int i=0;i<(1<<p);i++){ 104 if(i>(i^t))continue; 105 add(i*maxn*maxn+x1*maxn+y1,(i^t)*maxn*maxn+x1*maxn+y1,0); 106 } 107 } 108 build(); 109 printf("%d ",spfa()); 110 } 111 return 0; 112 }