传送门
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
上一篇：[TyvjP1515] 子串统计 [luoguP2408] 不同子串个数（后缀数组）
下一篇：[POJ3974]Palindrome（后缀数组 || manacher）
spfa 最短路
