首先关于分层图思想详见2004的这个论文
https://wenku.baidu.com/view/dc57f205cc175527072208ad.html
这道题可以用状态压缩，我们对于每一把钥匙的状态只有两种，获得了或者没有获得，然后就可以用二进制方法表示，例如一共有5把钥匙，我们如果用二进制数01001表示当前状态，就意味着我们已经拥有了第一类钥匙，第四类钥匙（从右往左看），然后我们就可以把此时的状态压缩为一个int了，节省了很多的空间，具体的操作就用位运算实现。
然后就是简单粗暴的dfs过程。
不过有几个点需要注意
① 要加反边。
② 一个位置可能有多个钥匙，注意要用位与运算。
下面给出代码。
1 #include <cstdio>
2 #include <queue>
3 #include <cstring>
4 using namespace std;
5 const int N = 20;
6
7 struct Node{
8 int x, y, step, state;
9 };
10 int n, m, p, t, tt, map[N][N][N][N], key[N][N], vis[N][N][1 << 11];
11 int py[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
12
13 inline int bfs(){
14 queue < Node > q;
15 q.push((Node){1, 1, 0, key[1][1]});
16 while(!q.empty()){
17 Node u = q.front(); q.pop();
18 if (u.x == n && u.y == m) return u.step;
19 for (int i = 0; i < 4; i++){
20 int x = u.x + py[i][0];
21 int y = u.y + py[i][1];
22 if (x > 0 && x <= n && y > 0 && y <= m)
23 if (map[u.x][u.y][x][y] == -1) continue;
24 else if((map[u.x][u.y][x][y] == 0) || (1 << (map[u.x][u.y][x][y] - 1)) & u.state){
25 int states = u.state | key[x][y];
26 if (!vis[x][y][states]){
27 q.push((Node){x, y, u.step + 1, states});
28 vis[x][y][states] = 1;
29 }
30 }
31 }
32 }
33 return -1;
34 }
35
36
37
38 int main(){
39 while(~scanf("%d %d %d",&n, &m, &p)){
40 scanf("%d", &t);
41 memset(map, 0, sizeof(map));
42 memset(key, 0, sizeof(key));
43 memset(vis, 0, sizeof(vis));
44 for (int i = 0; i < t; i++){
45 int a, b, c, d, e;
46 scanf("%d %d %d %d %d", &a, &b, &c, &d, &e);
47 map[a][b][c][d] = map[c][d][a][b] = (e == 0)?-1:e;
48 }
49 scanf("%d", &tt);
50 for (int i = 0; i < tt; i++){
51 int a, b, c;
52 scanf("%d %d %d", &a, &b, &c);
53 key[a][b] |= (1 << (c - 1));
54 }
55 printf("%d\n", bfs());
56 }
57 return 0;
58 }