UVA - 658 最短路

    思路：通过前后两种状态建立一条边，利用Dijsktra就可以做了。

   注意利用二进制优化。

AC代码

#include <cstdio>#include <cmath>#include <algorithm>#include <cstring>#include <utility>#include <string>#include <iostream>#include <map>#include <set>#include <vector>#include <queue>#include <stack>using namespace std;#PRagma comment(linker, "/STACK:1024000000,1024000000") #define eps 1e-10#define inf 0x3f3f3f3f#define PI pair<int, int> typedef long long LL;const int maxn = (1 << 20) + 5, maxm = 100 + 5;int n, m, d[maxn], vis[maxn];char before[maxm][25], after[maxm][25];int cost[maxm]; struct Node{	int bug, dist;	Node(){}	Node(int bug, int dis):bug(bug),dist(dis){}	bool Operator < (const Node& p) const {		return dist > p.dist;	}};int Dijsk(int u) {	memset(d, inf, sizeof(d));	memset(vis, 0, sizeof(vis));	priority_queue<Node>Q;	Q.push(Node(u, 0));	d[u] = 0;	while(!Q.empty()) {		Node p = Q.top(); Q.pop();		int u = p.bug;		if(u == 0) return d[u];		if(vis[u]) continue;		vis[u] = 1;		for(int i = 0; i < m; ++i) {			bool ok = true;			for(int j = 0; j < n; ++j) {				if(before[i][j] == '+' && !(u & (1 << j))) {ok = false; break;}				if(before[i][j] == '-' && (u & (1 << j))) {ok = false; break;}			}			if(!ok) continue; //不能打补丁 			Node v = Node(u, p.dist + cost[i]);			for(int j = 0; j < n; ++j) {				if(after[i][j] == '-') v.bug &= ~(1 << j);				if(after[i][j] == '+') v.bug |= (1 << j);			}			if(v.dist < d[v.bug] || d[v.bug] < 0) {				d[v.bug] = v.dist;				Q.push(v);			}		}	}	return -1;}int main() {	int kase = 0;	while(scanf("%d%d", &n, &m) == 2 && n && m) {		for(int i = 0; i < m; ++i) {			scanf("%d%s%s", &cost[i], before[i], after[i]);		}		int ans = Dijsk((1 << n) - 1);		printf("Product %d/n", ++kase);		if(ans == -1) printf("Bugs cannot be fixed./n");		else printf("Fastest sequence takes %d seconds./n", ans);		printf("/n");	}	return 0;}如有不当之处欢迎指出！