BFS + 状压
写过就好想,注意细节debug
#include <bits/stdc++.h>
#define read read()
#define up(i,l,r) for(register int i = (l);i <= (r);i++)
#define down(i,l,r) for(register int i = (l);i >= (r);i--)
#define traversal_vedge(i) for(register int i = head[u]; i ;i = e[i].nxt)
#define ll long long
using namespace std;
int read
{
int x = , f = ; char ch = getchar();
while(ch < || ch > ) {if(ch == '-')f = -; ch = getchar();}
while(ch >= && ch <=) {x = * x + ch - ;ch = getchar();}
return x * f;
}
void write(int x)
{
if(x < ) x = -x,putchar('-');
if(x > ) write(x/);
putchar(x% + );
}
//-----------------------------------------------------------------
const int N = ;
int n,m,p,k,s;
int maps[N][N][N][N],cnt[N][N],type[N][N][N],vis[N][N][(<<N)];
int dx[] = {,,,-,},dy[] = {,-,,,}; void readdata()
{
n = read; m = read; p = read; k = read;
int x1,x2,y1,y2,G;
while(k--)
{
x1 = read; y1 = read; x2 = read; y2 = read; G = read;
if(G) maps[x1][y1][x2][y2] = maps[x2][y2][x1][y1] = G;
else maps[x1][y1][x2][y2] = maps[x2][y2][x1][y1] = -;
}
s = read; int q;
while(s--)
{
x1 = read; x2 = read; q = read;
type[x1][x2][++cnt[x1][x2]] = q;
}
} struct node{
int x,y,step,state;
}; int get_state(int x,int y)
{
int ans = ;
up(i,,cnt[x][y]) ans |= (<<(type[x][y][i] - ));
return ans;
} int bfs()
{
queue <node> q;
int s = get_state(,);
q.push((node){,,,s} );
vis[][][s] = ;
while(!q.empty())
{
node u = q.front(); q.pop();
int x = u.x,y = u.y;
if(x == n && y == m) return u.step;
up(i,,)
{
int nx = x + dx[i],ny = y + dy[i];
if(nx < || ny < || nx > n || ny > m) continue;
int obstacle = maps[x][y][nx][ny];
if(obstacle == -) continue;
if( obstacle > && (u.state & <<(obstacle - )) == ) continue;//debug obstacle - 1 <- 1 - obstacle
int ns = u.state|get_state(nx,ny);//degug u.state <- s;
if(vis[nx][ny][ns]) continue;
vis[nx][ny][ns] = ;
q.push( (node){nx,ny,u.step+,ns} );
}
}
return -;
} int main()
{
freopen("input.txt","r",stdin);
readdata();
printf("%d\n",bfs());
return ;
}