传送门
吐槽：神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
上一篇：[luoguP2024] 食物链（并查集）
下一篇：[POJ3728]The merchant（tanrjan_lca + DP）
最短路 spfa
