题意：
有n个BUG和m个补丁，每个补丁用一个串表示打补丁前的状态要满足的要求，第二个串表示打完后对补丁的影响，还有打补丁所需要的时间。
求修复所有BUG的最短时间。
分析：
可以用n个二进制位表示这n个BUG的当前状态。最开始时所有BUG都存在，所以状态为n个1.目标状态是0
当打上一个补丁时，状态就会发生转移。因为有可能一个补丁要打多次，所以这个图不是DAG。
可以用Dijkstra算法，求起始状态到终态的最短路。代码中用了优先队列优化。
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std; const int maxn = ;
const int maxm = + ;
const int INF = ; int n, m, t[maxm], dist[<<maxn], mark[<<maxn];
char before[maxm][maxn + ], after[maxm][maxn + ]; struct Node
{
int bugs, dist;
bool operator < (const Node& rhs) const
{//优先级大的排在前面，老是弄错=_=||
return dist > rhs.dist;
}
}; int solve()
{
for(int i = ; i < (<<n); ++i) { dist[i] = INF; mark[i] = ; }
priority_queue<Node> q; Node start;
start.dist = ;
start.bugs = (<<n) - ; dist[start.bugs] = ;
q.push(start); while(!q.empty())
{
Node u = q.top(); q.pop();
if(u.bugs == ) return u.dist;
if(mark[u.bugs]) continue;
mark[u.bugs] = ;
for(int i = ; i < m; ++i)
{
bool flag = true;
for(int j = ; j < n; ++j)
{//是否满足打补丁的条件
if(before[i][j] == '+' && !(u.bugs & (<<j))) { flag = false; break; }
if(before[i][j] == '-' && u.bugs & (<<j) ) { flag = false; break; }
}
if(!flag) continue; Node u2;
u2.dist = u.dist + t[i];
u2.bugs = u.bugs;
for(int j = ; j < n; ++j)
{//打完补丁以后的状态
if(after[i][j] == '+') u2.bugs |= ( << j);
if(after[i][j] == '-') u2.bugs &= ~( << j);
}
int &D = dist[u2.bugs];
if(u2.dist < D)
{
D = u2.dist;
q.push(u2);
}
}
} return -;
} int main()
{
//freopen("in.txt", "r", stdin); int kase = ;
while(scanf("%d%d", &n, &m) == && n && m)
{
for(int i = ; i < m; ++i) scanf("%d%s%s", &t[i], before[i], after[i]);
int ans = solve();
printf("Product %d\n", ++kase);
if(ans < ) puts("Bugs cannot be fixed.\n");
else printf("Fastest sequence takes %d seconds.\n\n", ans);
} return ;
}
代码君