UVA - 658 It's not a Bug, it's a Feature! （隐式图的最短路，位运算）

隐式的图搜索，存不下边，所以只有枚举转移就行了，因为bug的存在状态可以用二进制表示，转移的时候判断合法可以用位运算优化，

二进制pre[i][0]表示可以出现的bug，那么u&pre[i][0] == u就表示u是可以出现的bug集合的子集，

pre[i][1]表示必须出现的bug，那么u|pre[i][i] != u表示把必须出现的bug添加到u中，u中bug增加表面bug不全在u中，这是不合法的。

正权最短路就dijkstra，用spfa以前某题狂T有阴影。被输出格式坑得不要不要的，如果是if(kas) putchar('\n');就会WA...

#include<bits/stdc++.h>

using namespace std;

const int maxm = ;

const int maxn = ;

int pre[maxm][],nxt[maxm][];

int cost[maxm];

int n,m;

int dist[<<maxn];

typedef pair<int,int> Node;

#define fi first

#define se second

//bitset<20> temp;

#define bug(u)\

temp = u; cout<<#u<<'='<<temp<<endl;

#define cer(x)\

cout<<"dist="<<x<<endl;

const int INF = 0x3f3f3f3f;

void dijkstra()

{

    priority_queue<Node,vector<Node>,greater<Node> > q;

    memset(dist,0x3f,sizeof(int)*(<<n));

    q.push(Node(,(<<n)-));

    dist[(<<n)-] = ;

    while(q.size()){

        Node x = q.top(); q.pop();

        if(x.se == )  { printf("Fastest sequence takes %d seconds.\n",dist[]); return; }

        if(x.fi != dist[x.se]) continue;

        int u = x.se;

        for(int i = ; i < m; i++){

            if( (pre[i][]&u) == u && (pre[i][]|u) == u){

                int v = (u&nxt[i][])|nxt[i][];

                if(dist[v] > dist[u]+cost[i]){

                    dist[v] = dist[u] + cost[i];

                    q.push(Node(dist[v],v));

                }

            }

        }

    }

    puts("Bugs cannot be fixed.");

}

int main()

{

    //freopen("in.txt","r",stdin);

    int kas = ;

    char s1[maxn+],s2[maxn+];

    while(scanf("%d%d",&n,&m),n){

        for(int i = ; i < m ; i++){

            scanf("%d%s%s",cost+i,s1,s2);

            nxt[i][] = nxt[i][] = pre[i][] = pre[i][] = ;

            for(int j = ; j < n; j++){

                if(s1[j] == '+') pre[i][] |= <<j;

                if(s1[j] != '-') pre[i][] |= <<j;

                if(s2[j] == '+') nxt[i][] |= <<j;

                if(s2[j] != '-') nxt[i][] |= <<j;

            }

        }

        printf("Product %d\n",++kas);

        dijkstra();

        putchar('\n');

    }

    return ;

}

UVA - 658 It's not a Bug, it's a Feature! （隐式图的最短路，位运算）的相关教程结束。