UVA 658，我在本地测过样例了，但交上去就WA求指点。

Question

题目链接

#include<bits/stdc++.h>
using namespace std;

struct Node
{
    int bug;
    int dis;
    bool operator < (const Node &other) const
    {
        return dis < other.dis;
    }
};

struct patch
{
    unsigned need;
    unsigned absent;
    unsigned fix;
    unsigned introduce;
    unsigned w;
}u[105];

void init(patch &k,int n)
{
    k.need = 0;//需要为1，不需要为0，need|bug == bug
    k.absent = (1<<n)-1;//允许为1，不允许为0，absent&bug == bug
    k.fix = (1<<n)-1;//可修复为0，其他为1，bug = bug&fix 
    k.introduce = 0; //会被制造出的为1，其他为0，bug = bug|introduce 
}

int dis[1<<20+5];
bool book[1<<20+5];

int main()
{
    int n,m,T=1;
    while(scanf("%d%d",&n,&m)==2)
    {
        if(n==0&&m==0)break;
        memset(dis,0x3f,sizeof(dis));
        memset(book,false,sizeof(book));
        printf("Product %d\n",T);
        T++;
        bool flag=false;
        Node now;
        now.bug = now.dis = 0;
        now.bug = (1<<n) - 1;
        dis[now.bug] = 0;
        book[now.bug] = true;
        priority_queue <Node> q;
        q.push(now);
        for(int i=0;i<m;i++)
        {
            init(u[i],n);
            scanf("%d",&u[i].w);
            char a[25];
            scanf("%s",a);
            for(int j = 0;j < n;j++)
            {
                if(a[j]=='+')
                    u[i].need = u[i].need + (1<<j);
                else if(a[j]=='-')
                    u[i].absent = u[i].absent - (1<<j);
            }
            scanf("%s",a);
            for(int j = 0;j < n;j++)
            {
                if(a[j]=='+')
                    u[i].introduce = u[i].introduce | (1<<j);
                else if(a[j]=='-')
                    u[i].fix = u[i].fix - (1<<j);
            }
        }
        while(!q.empty())
        {
            int nb = q.top().bug,nd = q.top().dis;
            q.pop();
            while(book[nb] && !q.empty() )
            {
                nb = q.top().bug,nd = q.top().dis;
                q.pop();
            }
            book[nb] = true;
            if(nb == 0)
            {
                flag=true;
                printf("Fastest sequence takes %d seconds.\n\n",nd);
                break;
            }
            for(int i=0;i<m;i++)
            {
                if((u[i].need | nb) == nb && (u[i].absent & nb) == nb)
                {
                    now.bug= (nb&u[i].fix)|u[i].introduce;
                    now.dis= nd + u[i].w;
                    if(now.dis<dis[now.bug])
                    {
                        dis[now.bug] = now.dis;
                        q.push(now); 
                    }
                }
            }
        }
        if(!flag)
            printf("Bugs cannot be fixed.\n\n");
    }
}

Answer 1

uDebug试试。我的uDebug都通过还是WA。