孤島營救問題
Description
1944 年，特種兵麥克接到國防部的命令，要求立即趕赴太平洋上的一個孤島，營救被敵軍俘虜的大兵瑞恩。瑞恩被關押在一個迷宮里，迷宮地形復雜，但幸好麥克得到了迷宮的地形圖。迷宮的外形是一個長方形，其南北方向被劃分為 N 行，東西方向被劃分為 M 列，于是整個迷宮被劃分為 N×M 個單元。每一個單元的位置可用一個有序數對(單元的行號，單元的列號)來表示。南北或東西方向相鄰的 2 個單元之間可能互通，也可能有一扇鎖著的門，或者是一堵不可逾越的墻。迷宮中有一些單元存放著鑰匙，并且所有的門被分成 P 類，打開同一類的門的鑰匙相同，不同類門的鑰匙不同。 大兵瑞恩被關押在迷宮的東南角，即(N，M)單元里，并已經昏迷。迷宮只有一個入口，在西北角。也就是說，麥克可以直接進入(1，1)單元。另外，麥克從一個單元移動到另一個相鄰單元的時間為 1，拿取所在單元的鑰匙的時間以及用鑰匙開門的時間可忽略不計。 試設計一個算法，幫助麥克以最快的方式到達瑞恩所在單元，營救大兵瑞恩。
第 1 行有 3 個整數，分別表示 N,M,P 的值。第 2 行是 1 個整數 K，表示迷宮中門和墻的總數。第 I+2 行（1<=I<=K），有 5 個整數，依次為Xi1,Yi1,Xi2,Yi2,Gi： 當 Gi>=1 時，表示(Xi1,Yi1)單元與(Xi2,Yi2)單元之間有一扇第 Gi 類的門，當 Gi=0 時，表示(Xi1,Yi1)單元與(Xi2,Yi2)單元之間有一堵不可逾越的墻（其中，|Xi1-Xi2|+|Yi1-Yi2|=1，0<=Gi<=P）。 第 K+3 行是一個整數 S，表示迷宮中存放的鑰匙總數。 第 K+3+J 行(1<=J<=S)，有 3 個整數，依次為 Xi1,Yi1,Qi：表示第 J 把鑰匙存放在(Xi1,Yi1)單元里，并且第 J 把鑰匙是用來開啟第 Qi 類門的。（其中 1<=Qi<=P）。 輸入數據中同一行各相鄰整數之間用一個空格分隔。
Output
輸出麥克營救到大兵瑞恩的最短時間的值。 如果問題無解，則輸出-1。
Hint
N,M,P <= 10 K < 150
題解
網絡流？？？喵喵喵？？？ 分層圖思想。門的數目很小，可以用二進制實現狀態壓縮。而對這2P個狀態可以對應的建2P個圖跑SPFA即可，當然圖不用真的建出來，每次判斷能不能走并在層間轉移即可，具體實現看代碼。
#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>#include<queue>using namespace std;const int N = 200, M = 160000, P = 1<<15, inf = 0x3f3f3f3f;const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};struct Node{ int x, y, z; Node(int a, int b, int c){x = a, y = b, z = c;}};int n, m, p, k, s;int idx[N][N], mp[N][N], inq[N][P], d[N][P], key[N];int ans;void init(){ scanf("%d%d%d%d", &n, &m, &p, &k); int u, v, w; for(int i = 1, t = 0; i <= n; i++) for(int j = 1; j <= m; j++) idx[i][j] = ++t; for(int i = 1; i <= k; i++){ scanf("%d%d", &u, &v); u = idx[u][v]; scanf("%d%d", &v, &w); v = idx[v][w]; scanf("%d", &w); if(!w) mp[u][v] = mp[v][u] = -1; else mp[u][v] = mp[v][u] |= 1 << w; } scanf("%d", &s); for(int i = 1; i <= s; i++){ scanf("%d%d%d", &u, &v, &w); key[idx[u][v]] |= 1 << w; }}void work(){ memset(d, 0x3f, sizeof(d)); d[idx[1][1]][0] = 0; queue<Node> q; q.push(Node(1, 1, 0)); inq[idx[1][1]][0] = 1; while(!q.empty()){ Node u = q.front(); q.pop(); int now = idx[u.x][u.y]; inq[now][u.z] = false; for(int i = 0; i < 4; i++){ int r = u.x + dx[i]; int c = u.y + dy[i]; if(r > 0 && r <= n && c > 0 && c <= m){ int next = idx[r][c]; if(mp[next][now] != -1) if(d[next][u.z] > d[now][u.z] + 1) if((u.z & mp[next][now]) == mp[next][now]){ d[next][u.z|key[next]] = d[next][u.z] = d[now][u.z] + 1; if(!inq[next][u.z|key[next]]){ q.push(Node(r, c, u.z|key[next])); inq[next][u.z|key[next]] = 1; } } } } } ans = inf; for(int i = 0; i < (1<<p+1); i++) ans = min(ans, d[idx[n][m]][i]); if(ans == inf) puts("-1"); else
