UVA 658 It‘s not a Bug, it‘s a Feature!

题意：给出m个长为n的字符串 （2个）s1,s2. 表示这个补丁打之前要是s1的状态，打完之后就变成s2的状态。然后每个补丁有一个执行时间，初始状态是都有bug，问你最少用多少时间把这些bug全部修好。 分析：由于补丁可以任意地打和不打，所以当修完补丁后，很可能会回到以前的状态，说明这个关系是一个DAG，有向无环图，如果使用记忆化搜索或者dp都是错误的，因为在递归时上一个状态还没计算完成，就回到了以前的状态，造成无限递归。dp与图论息息相关，我们把补丁看作状态，用一个二进制数s表示当前的bug有没有，打完补丁又变成了下一个状态。把状态看作顶点，转移花费（执行时间）看作边权，问题显然转化为最短路. 但问题还没解决！顶点太多了高达2的20次方！ 但注意，有些顶点根本是没有办法达到的，因为m很小，不可能每个点都有用，所以我们没有必要把完整的图建立出来，而是使用隐式图搜索的思路，每次到达一个点，不是去枚举它的边，而是直接枚举m个补丁（枚举所有的边，因为m非常小）。 代码：

#include
using namespace std;
int n,m;
const int maxn=(1