UVA658 这不是bug，而是特性 It's not a Bug, it's a Feature! 题解

· · 题解

思路

每个 bug 可能存在也可能不存在，那么不难看出可以尝试使用二进制，再一看是最小时间，不难想出可以模拟最短路用 Dijkstra 算法。

代码实现

#include<bits/stdc++.h>
using namespace std;
inline void rd(int &x){
    x=0;char ch;
    bool f=false;
    for(ch=getchar();ch<'0'||ch>'9';ch=getchar())
        if (ch=='-')
            f=true;
    for(;ch>='0'&&ch<='9';ch=getchar())
        x=(x<<3)+(x<<1)+(ch&15);
    if (f) x=-x;
}
inline void wr(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9) wr(x/10);
    putchar(x%10+'0');
    return;
}//快读写
const int N=1<<20;
int n,m,s,a[N],b[N],c[N],d[N],l;
long long dis[N],t[N];
set<pair<long,int> >q;
void Dijkstra(){
    memset(dis,0x3f,sizeof dis);
    dis[s]=0;
    q.insert({0,s});
    while(!q.empty()){
        int x=q.begin()->second;
        q.erase(q.begin());
        for(int i=1;i<=m;i++){
            if(((x&a[i])==a[i])&(x&b[i])==0){
                int y=(x|c[i])&d[i];
                if(dis[y]>dis[x]+t[i]){
                    dis[y]=dis[x]+t[i];
                    q.insert({dis[y],y});
                }
            }
        }
    }
}
int main(){
    while(1){
        rd(n),rd(m);
        if(n==0&&m==0)break;
        s=(1<<n)-1;
        for(int i=1;i<=m;i++){
            string c1,c2;
            cin>>t[i]>>c1>>c2;
            a[i]=0;b[i]=0;c[i]=0;
        for(int j=0;j<n;j++){
                if(c1[j]=='+')a[i]|=(1<<j);
                else if(c1[j]=='-')b[i]|=(1<<j);
                d[i]=s;
            }
            for(int j=0;j<n;j++){
                if(c2[j]=='+')c[i]|=(1<<j);
                else if(c2[j]=='-')d[i]^=(1<<j);
            }
        }//二进制
        Dijkstra();
        cout<<"Product "<<++l<<endl;
        if(dis[0]==0x3f3f3f3f3f3f3f3f)cout<<"Bugs cannot be fixed."<<endl;
        else cout<<"Fastest sequence takes "<<dis[0]<<" seconds."<<endl;
        cout<<endl;
    }
    return 0;
}