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

传送门

吐槽：神tm网络流。。。

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

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

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

——代码

1 #include <queue> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #define N 20 6 #define min(x, y) ((x) < (y) ? (x) : (y)) 7 8 int n, m, p, ans = ~(1 << 31); 9 int map[N][N][N][N], key[N][N], dis[N][N][1 << 11]; 10 int dx[4] = , dy[4] = ; 11 bool vis[N][N][1 << 11]; 12 13 struct node 14 17 }; 18 19 std::queue <node> q; 20 21 inline int read() 22 29 30 inline bool Acc(int x1, int y1, int x2, int y2, int s) 31 37 38 inline void spfa() 39 65 } 66 } 67 } 68 } 69 70 int main() 71 86 keys = read(); 87 for(i = 1; i <= keys; i++) 88 94 spfa(); 95 for(i = 0; i < (1 << 11); i++) ans = min(ans, dis[n][m][i]); 96 if(ans == 7074078) ans = 1; 97 printf("%d\n", ans); 98 return 0; 99 }
View Code

上一篇：[HDU2328]Corporate Identity（后缀数组）

下一篇：[POJ1733]Parity game（并查集 + 离散化）

---

spfa 最短路