[luoguP2761] 软件补丁问题（状压最短路）

传送门

n <= 20 很小

所以可以状态压缩

然后因为可能存在环，所以不能DP

那么就用spfa找最短路

被位运算坑了，不清楚优先级一定要加括号

——代码

1 #include <queue> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #define M 301 6 #define N 0001 7 8 int n, m; 9 int b1[M], b2[M], f1[M], f2[M], a[M], dis[N]; 10 bool vis[N]; 11 12 inline void spfa() 13 35 } 36 } 37 } 38 } 39 40 int main() 41 55 } 56 spfa(); 57 dis[0] == dis[1 << n] ? puts("0") : printf("%d\n", dis[0]); 58 return 0; 59 }
View Code

上一篇：[luoguP1251] 餐巾计划问题（费用流）

下一篇：[POJ3974]Palindrome（后缀数组 || manacher）

---

spfa 最短路