[CODEVS1911] 孤岛营救问题（分层图最短路）

传送门

吐槽：神tm网络流。。。

用持有的钥匙分层，状态压缩，用 2 进制表示持有的钥匙集合。

dis[i][j][k] 表示持有的钥匙集合为 k，到达点 (i, j) 的最短路径。

分层图的最短路听上去很玄乎，其实通过代码来看还是很好理解的。

——代码

 #include <queue>

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #define N 20

 #define min(x, y) ((x) < (y) ? (x) : (y))

 int n, m, p, ans = ~( << );

 int map[N][N][N][N], key[N][N], dis[N][N][ << ];

 int dx[] = {, , , -}, dy[] = {, , -, };

 bool vis[N][N][ << ];

 struct node

 {

     int x, y, s;

     node(int x = , int y = , int s = ) : x(x), y(y), s(s) {}

 };

 std::queue <node> q;

 inline int read()

 {

     int x = , f = ;

     char ch = getchar();

     for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -;

     for(; isdigit(ch); ch = getchar()) x = (x << ) + (x << ) + ch - '';

     return x * f;

 }

 inline bool Acc(int x1, int y1, int x2, int y2, int s)

 {

     int need_key = map[x1][y1][x2][y2];

     if(!need_key) return ;

     if(need_key == -) return ;

     return (s >> need_key - ) & ;

 }

 inline void spfa()

 {

     node now;

     int i, s, x, y;

     memset(dis,  / , sizeof(dis));

     dis[][][] = ;

     q.push(node(, , ));

     while(!q.empty())

     {

         now = q.front();

         q.pop();

         vis[now.x][now.y][now.s] = ;

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

         {

             x = now.x + dx[i];

             y = now.y + dy[i];

             s = now.s | key[x][y];

             if(!x || x > n || !y || y > m) continue;

             if(Acc(now.x, now.y, x, y, now.s))

                 if(dis[x][y][s] > dis[now.x][now.y][now.s] + )

                 {

                     dis[x][y][s] = dis[now.x][now.y][now.s] + ;

                     if(!vis[x][y][s])

                     {

                         vis[x][y][s] = ;

                         q.push(node(x, y, s));

                     }

                 }

         }

     }

 }

 int main()

 {

     int i, j, a, b, c, d, x, y, z, doors, keys;

     n = read();

     m = read();

     p = read();

     doors = read();

     memset(map, -, sizeof(map));

     for(i = ; i <= doors; i++)

     {

         a = read();

         b = read();

         c = read();

         d = read();

         map[a][b][c][d] = map[c][d][a][b] = read();

     }

     keys = read();

     for(i = ; i <= keys; i++)

     {

         x = read();

         y = read();

         z = read();

         key[x][y] |=  << z - ;

     }

     spfa();

     for(i = ; i < ( << ); i++) ans = min(ans, dis[n][m][i]);

     if(ans == ) ans = -;

     printf("%d\n", ans);

     return ;

 }