/*
可以这很强势
一遍写完调试了两分钟过了样例直接AC秒杀~
和P1026很像    都是可以位运算处理然后转换SPFA
当然bfs+hash也是可以的
题目的确有点繁琐(当初看到这个逃了好几次)
但是静下心来仔细看就好了
check函数和get函数很精妙
位运算又进一步加强了
这种题目还是要自己多写写好
详细看P1026的题解叭~~~
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

const int MAXN=(1<<16)-1;
const int MAXM=102;
const int INF=(1<<30)-1;
int B1[MAXM],B2[MAXM];
int F1[MAXM],F2[MAXM];
bool in[MAXN];
queue<int> q;
int t[MAXM];
int d[MAXN];
int n,m;
int s;

void init()
{
    string a,b;
    cin>>n>>m;
    s=(1<<n)-1;
    for(int i=1;i<=m;i++)
    {
        cin>>t[i]>>a>>b;
        for(int j=0;j<n;j++)
            if(a[j]=='+')
                B1[i]|=(1<<j);
            else    if(a[j]=='-')
                B2[i]|=(1<<j);
        for(int j=0;j<n;j++)
            if(b[j]=='-')
                F1[i]|=(1<<j);
            else    if(b[j]=='+')
                F2[i]|=(1<<j);
    }
    for(int i=0;i<MAXN;i++)
        d[i]=INF;
}

bool check(int x,int k)
{
    for(int i=0;i<n;i++)
        if((1<<i)&B1[k]&&(!((1<<i)&x)))
            return 0;
    for(int i=0;i<n;i++)
        if((1<<i)&B2[k]&&(1<<i)&x)
            return 0;
    return 1;
}

int get(int x,int k)
{
    x&=(~F1[k]);
    x|=F2[k];
    return x;
}

void SPFA()
{
    d[s]=0; q.push(s);  in[s]=1;
    while(!q.empty())
    {
        int u=q.front();    q.pop();
        in[u]=0;
        for(int i=1;i<=m;i++)
        {
            if(!check(u,i))
                continue;
            int v=get(u,i);
            if(d[v]>d[u]+t[i])
            {
                d[v]=d[u]+t[i];
                if(!in[v])
                {
                    q.push(v);
                    in[v]=1;
                }
            }
        }
    }
    if(d[0]==INF)
        cout<<0<<endl;
    else
        cout<<d[0]<<endl;
}

int main()
{
    init();
    SPFA();
    return 0;
}
     

貌似就我一个人傻傻的用dfs。贴一下吧，虽然速度不咋地- -
//位运算+dfs

#include<iostream>
#include<math.h>
#include<string>
#include<memory.h>
using namespace std;
const int MAXN = 15;
const int MAXM = 101;
const int MAXV = 32768;
const int MAXT = 10000000;

typedef pair<int, int> P ;

struct Node {
    int time;
    P con[MAXN];
    int clen;
    P tra[MAXN];
    int tlen;
}nodes[MAXM];
bool vis[MAXV];
int n, m;
int tans = 0;
int ans = MAXT;

bool OK(int sta, Node node) {
    int k;
    for (int i = 0; i<node.clen; i++) {
        k = node.con[i].first;
        if ((1 & (sta >> k)) != node.con[i].second)
            return 0;
    }
    return 1;
}

int nextSta(int sta, Node node) {
    int k;
    for (int i = 0; i<node.tlen; i++) {
        k = node.tra[i].first;
        sta = sta - ((1 << k)&sta) + (node.tra[i].second << k);
    }
    return sta;
}

void dfs(int sta) {
    vis[sta] = 1;
    if (tans >= ans);
    else if (sta == 0) {
        if (tans<ans)
            ans = tans;
    }
    else {
        int nextsta;
        for (int i = 0; i<m; i++) {
            if (OK(sta, nodes[i])) {
                nextsta = nextSta(sta, nodes[i]);
                if (!vis[nextsta]) {
                    tans += nodes[i].time;
                    dfs(nextsta);
                    tans -= nodes[i].time;
                }
            }
        }
    }
    vis[sta] = 0;
}

int main() {
    cin >> n >> m;
    string str1, str2;
    int i, j;
    for (i = 0; i<m; i++) {
        cin >> nodes[i].time >> str1 >> str2;
        nodes[i].clen = 0;
        nodes[i].tlen = 0;
        for (j = 0; j<n; j++) {
            switch (str1[j]) {
            case '0':
                break;
            case '+':
                nodes[i].con[nodes[i].clen].first = j;
                nodes[i].con[nodes[i].clen].second = 1;
                nodes[i].clen++;
                break;
            case '-':
                nodes[i].con[nodes[i].clen].first = j;
                nodes[i].con[nodes[i].clen].second = 0;
                nodes[i].clen++;
                break;
            }
            switch (str2[j]) {
            case '0':
                break;
            case '+':
                nodes[i].tra[nodes[i].tlen].first = j;
                nodes[i].tra[nodes[i].tlen].second = 1;
                nodes[i].tlen++;
                break;
            case '-':
                nodes[i].tra[nodes[i].tlen].first = j;
                nodes[i].tra[nodes[i].tlen].second = 0;
                nodes[i].tlen++;
                break;
            }
        }
    }
    memset(vis, 0, sizeof(vis));
    dfs((1 << n) - 1);
    if (ans != MAXT)
        cout << ans << endl;
    else
        cout << 0 << endl;
    return 0;
}

状态

耗时

内存占用

#1  Accepted  4ms 2.469MiB
#2  Accepted  3ms 2.5MiB
#3  Accepted  3ms 2.375MiB
#4  Accepted  3ms 2.5MiB
#5  Accepted  4ms 2.375MiB
#6  Accepted  3ms 2.375MiB
#7  Accepted  3ms 2.379MiB
#8  Accepted  4ms 2.375MiB
#9  Accepted  6ms 6.367MiB
#10  Accepted  4ms 2.5MiB

扔题解骗流量QAQ

此题由于n<=15，而2^15<35000因此可以使用状态压缩
那么可以想到一个简单的搜索，每一次判断可以用的补丁就补上。
这样的搜索加上hash判重以及最优性剪枝速度是比较快的。
代码如下：

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
    int num=0,bj=1;
    char x=getchar();
    while(x<'0'||x>'9') {
        if(x=='-')bj=-1;
        x=getchar();
    }
    while(x>='0'&&x<='9') {
        num=num*10+x-'0';
        x=getchar();
    }
    return num*bj;
}
int n,m,ans=0x7fffffff/2,Time[105],Use[105][25],Effect[105][25],Hash[70005];
bool Check(int state,int num) {
    for(int i=1; i<=n; i++) {
        if(!(state&(1<<(i-1)))&&Use[num][i]==1)return false;
        if((state&(1<<(i-1)))&&Use[num][i]==-1)return false;
    }
    return true;
}
void Dfs(int state,int ttime) {
    if(ttime>ans)return;
    if(Hash[state]<=ttime)return;
    Hash[state]=ttime;
    if(state==0) {
        ans=min(ans,ttime);
        return;
    }
    int nextstate;
    for(int i=1; i<=m; i++) {
        if(!Check(state,i))continue;
        nextstate=state;
        for(int j=1; j<=n; j++)
            if((state&(1<<(j-1)))&&Effect[i][j]==-1)nextstate^=1<<(j-1);
            else if(!(state&(1<<(j-1)))&&Effect[i][j]==1)nextstate^=1<<(j-1);
        Dfs(nextstate,ttime+Time[i]);
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1; i<=m; i++) {
        cin>>Time[i];
        for(int j=1; j<=n; j++) {
            char x;
            cin>>x;
            if(x=='-')Use[i][j]=-1;
            if(x=='+')Use[i][j]=1;
        }
        for(int j=1; j<=n; j++) {
            char x;
            cin>>x;
            if(x=='-')Effect[i][j]=-1;
            if(x=='+')Effect[i][j]=1;
        }
    } 
    memset(Hash,0x3f,sizeof(Hash));
    Dfs((1<<n)-1,0);
    if(ans==0x7fffffff/2)puts("0");
    else printf("%d\n",ans);
    return 0;
}

仔细思考，这样的搜索本质其实与最短路没有区别。
将状态看作点，状态转移看作边，时间是边权。
那么我们的hash判重其实就是spfa的inque数组，因此可以跑一遍最短路。
但实际上最短路更慢。

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
    int num=0,bj=1;
    char x=getchar();
    while(x<'0'||x>'9') {
        if(x=='-')bj=-1;
        x=getchar();
    }
    while(x>='0'&&x<='9') {
        num=num*10+x-'0';
        x=getchar();
    }
    return num*bj;
}
struct Edge {
    int from,to,dist;
};
vector<Edge>edges[35005];
int dist[35005],inque[35005],n,m,Time[105],Use[105][25],Effect[105][25];
void AddEdge(int x,int y,int v) {
    edges[x].push_back((Edge) {
        x,y,v
    });
}
void Spfa(int s) {
    memset(dist,0x3f,sizeof(dist));
    queue<int>Q;
    Q.push(s);
    inque[s]=1;
    dist[s]=0;
    while(!Q.empty()) {
        int Now=Q.front();
        inque[Now]=0;
        Q.pop();
        for(int i=0; i<edges[Now].size(); i++) {
            Edge& e=edges[Now][i];
            int Next=e.to;
            if(dist[Now]+e.dist<dist[Next]) {
                dist[Next]=dist[Now]+e.dist;
                if(!inque[Next]) {
                    inque[Next]=1;
                    Q.push(Next);
                }
            }
        }
    }
}
bool Check(int state,int num) {
    for(int i=1; i<=n; i++) {
        if(!(state&(1<<(i-1)))&&Use[num][i]==1)return false;
        if((state&(1<<(i-1)))&&Use[num][i]==-1)return false;
    }
    return true;
}
int Get_Next(int state,int num) {
    int nextstate=state;
    for(int j=1; j<=n; j++)
        if((state&(1<<(j-1)))&&Effect[num][j]==-1)nextstate^=1<<(j-1);
        else if(!(state&(1<<(j-1)))&&Effect[num][j]==1)nextstate^=1<<(j-1);
    return nextstate;
} 
int main() {
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1; i<=m; i++) {
        cin>>Time[i];
        for(int j=1; j<=n; j++) {
            char x;
            cin>>x;
            if(x=='-')Use[i][j]=-1;
            if(x=='+')Use[i][j]=1;
        }
        for(int j=1; j<=n; j++) {
            char x;
            cin>>x;
            if(x=='-')Effect[i][j]=-1;
            if(x=='+')Effect[i][j]=1;
        }
    } 
    for(int i=0; i<=(1<<n)-1; i++)
        for(int j=1; j<=m; j++)
            if(Check(i,j))AddEdge(i,Get_Next(i,j),Time[j]);
    Spfa((1<<n)-1);
    if(dist[0]==0x3f3f3f3f)puts("0");
    else printf("%d\n",dist[0]);
    return 0;
}

状态

耗时

内存占用

#1  Accepted  4ms 2.469MiB
#2  Accepted  3ms 2.5MiB
#3  Accepted  3ms 2.375MiB
#4  Accepted  3ms 2.5MiB
#5  Accepted  4ms 2.375MiB
#6  Accepted  3ms 2.375MiB
#7  Accepted  3ms 2.379MiB
#8  Accepted  4ms 2.375MiB
#9  Accepted  6ms 6.367MiB
#10  Accepted  4ms 2.5MiB

#include<cstdio>
#include<iostream>
#include<sstream>
#include<algorithm>
#include<string>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
const int inf=0x3f3f3f3f;
struct node
{
int tim;
vector<int>b1,b2,k1,k2;
}patch[110];
int n,m,ans=inf;
int vis[20];
int mi[25];
map<int,int>mapp;
bool check()
{
for(int i=1;i<=n;i++)
if(vis[i]) return false;
return true;
}
int Hash()
{
int sum=0;
for(int i=1;i<=n;i++)
sum=sum+mi[i]*vis[i];
return sum;
}
void dfs(int cost)
{
if(cost>=ans) return;
if(check())
{
ans=min(ans,cost);
return;
}
int temp[20];
for(int i=1;i<=n;i++)
temp[i]=vis[i];
for(int i=1;i<=m;i++)
{
int len=patch[i].b1.size(),flag=1;
for(int j=0;j<len;j++)
if(!vis[patch[i].b1[j]])
{
flag=0;
break;
}
if(flag)
{
len=patch[i].b2.size();
for(int j=0;j<len;j++)
if(vis[patch[i].b2[j]])
{
flag=0;
break;
}
}
if(!flag) continue;
len=patch[i].k2.size();
for(int j=0;j<len;j++)
vis[patch[i].k2[j]]=0;
len=patch[i].k1.size();
for(int j=0;j<len;j++)
vis[patch[i].k1[j]]=1;
int num=Hash();
if(!mapp.count(num))
{
mapp[num]=cost+patch[i].tim;
dfs(cost+patch[i].tim);
}
else if(mapp[num]>cost+patch[i].tim)
{
mapp[num]=cost+patch[i].tim;
dfs(cost+patch[i].tim);
}
for(int j=1;j<=n;j++)
vis[j]=temp[j];
}
}
int main()
{
int temp=1;
for(int i=1;i<=20;i++)
{
mi[i]=temp;
temp*=2;
}
cin>>n>>m;
string b,k;
for(int i=1;i<=m;i++)
{
cin>>patch[i].tim>>b>>k;
for(int j=0;j<n;j++)
if(b[j]=='+') patch[i].b1.push_back(j+1);
else if(b[j]=='-') patch[i].b2.push_back(j+1);
for(int j=0;j<n;j++)
if(k[j]=='+') patch[i].k1.push_back(j+1);
else if(k[j]=='-') patch[i].k2.push_back(j+1);
}
for(int i=1;i<=n;i++)
vis[i]=1;
mapp[Hash()]=0;
dfs(0);
if(ans==inf) cout<<"0";
else cout<<ans;
return 0;
}

位运算+SPFA，每个状态为一个点
#include <cstdio>
#include <cstring>
#include <queue>
#define add(A,K) A|=1<<K

int st,end,time[200];
int n,m;
int B[200]={0},B_[200]={0};
int F[200]={0},F_[200]={0};

void build(){
scanf("%d%d",&n,&m);
st=(1<<n)-1;
end=0;
char s1[100],s2[100];
for(int i=1;i<=m;i++){
scanf("%d",&time[i]);
scanf("%s%s",s1,s2);
for(int x=0;x<strlen(s1);x++){
if(s1[x]=='+')
add(B[i],x);
if(s1[x]=='-')
add(B_[i],x);
}
for(int x=0;x<strlen(s2);x++){
if(s2[x]=='+')
add(F[i],x);
if(s2[x]=='-')
add(F_[i],x);
}
}
}

int isok(int x,int way){
int flag=1;
flag*=(B[way]&x)==B[way];
flag*=(B_[way]&x)==0;
return flag;
}

int update(int x,int way){
x|=F[way];
x&=(~F_[way]);
return x;
}

//SPFA
std::queue<int> q;
int inque[1<<15+10]={0};
int dist[1<<15+10];

void spfa(){
dist[st]=0;
q.push(st);
inque[st]=1;
int t,temp;
while(!q.empty()){
t=q.front(),q.pop();
inque[t]=0;
for(int i=1;i<=m;i++){
if(!isok(t,i))
continue;
temp=update(t,i);
if(dist[t]+time[i]<dist[temp]){
dist[temp]=dist[t]+time[i];
if(!inque[temp]){
q.push(temp);
inque[temp]=1;
}
}
}

}

}

int main(){
for(int i=0;i<=(1<<15)+5;i++)
dist[i]=999999999;
build();
spfa();
if(dist[end]==999999999)
printf("0");
else
printf("%d",dist[end]);

return 0;
}

#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<queue>
using namespace std;

const int INF = 1000000000;
const int maxn = 15;
const int maxm = 100 + 10;
int n, m;
int  d[1<<maxn];
bool done[1<<maxn];

struct Patch {
    string s1, s2;
    int cost;
    Patch(string s1, string s2, int cost) : s1(s1), s2(s2), cost(cost) {}
};

vector<Patch> patchs;

struct HeapNode {
    int u, d;
    HeapNode (int u, int d) : u(u), d(d) {}
    bool operator < (const HeapNode& rhs) const {
        return d > rhs.d;
    }
};

bool check (int x, const string& s) {
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == '+' && !(x & (1<<i))) return false;
        if (s[i] == '-' && (x & (1<<i))) return false;
    }
    return true;
}

int add_patch (int x, const string& s) {
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == '+') x |= (1<<i);
        if (s[i] == '-' && (x & (1<<i))) x ^= (1<<i);
    }
    return x;
}

void djs (void) {
    priority_queue<HeapNode> Q;
    Q.push(HeapNode((1<<n)-1, 0));
    d[(1<<n)-1] = 0;
    
    while (!Q.empty()) {
        HeapNode x = Q.top(); Q.pop();
        int u = x.u;
        if (done[u]) continue;
        done[u] = true;
        
        for (int i = 0; i < patchs.size(); i++) 
            if (check(u, patchs[i].s1)) { 
                int to = add_patch(u, patchs[i].s2);
                if (d[u] + patchs[i].cost < d[to]) {
                    d[to] = d[u] + patchs[i].cost;
                    Q.push(HeapNode(to, d[to]));
                }
            }
    }
}

int main ()
{
//  freopen ("in.txt", "r", stdin);
    cin >> n >> m;
    int c;
    string s1, s2;
    for (int i = 0; i < m; i++) {
        cin >> c >> s1 >> s2;
        patchs.push_back(Patch(s1, s2, c));
    }
    
    for (int i = 0; i < (1<<n); i++) d[i] = INF;
    djs();
    if (d[0] >= INF) cout << 0 << "\n";
    else cout << d[0] << "\n";
    
    return 0;
}

数据真弱……

#include<cstdio>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;

const int INF = 2147483647;

struct Po
{
    int th,dis;
    Po(int a,int b) : th(a) , dis(b) {};
    bool operator> (Po const &a) const{return dis > a.dis; }
};

struct Ed
{
    int span;
    vector<char> nodetail;
    vector<char> fudetail;
    Ed(int a) : span(a) {};
};

int n,m;
bool vis[32800];
vector<Ed> edges;
vector<Po> points;
priority_queue<Po,vector<Po>,greater<Po> > Q;

bool is_ok(int now,int th,int &next)
{
    Ed &ed=edges[th];
    for(int i=0;i<n;i++)
    {
        if(ed.nodetail[i]=='+'&& (  ( now&(1<<(n-1-i)) )!=(1<<(n-1-i)) ) ) return false;
        if(ed.nodetail[i]=='-'&&  ((now&(1<<(n-1-i)))!=0))                   return false;
    }
    next=now;
    for(int i=0;i<n;i++)
    {
        if(ed.fudetail[i]=='+')  next=next|(1<<(n-1-i));
        if(ed.fudetail[i]=='-' && ((now&(1<<(n-1-i)))==(1<<(n-1-i))))   next=next-(1<<(n-1-i));
    }
    return true;
}

void djs()
{
    memset(vis,0,sizeof(vis));
    int b=(1<<n) -1;
    points[b].dis=0;
    Q.push(points[b]);
    while(!Q.empty())
    {
        int k=(Q.top()).th; Q.pop();
        if(vis[k]) continue;
        Po &now=points[k];vis[k]=true;
        int next;
        if(vis[0]) break;
        
        for(int i=0;i<(int)edges.size();i++)
            if(is_ok(k,i,next)&&!vis[next]&&points[next].dis>now.dis+edges[i].span)
            {
                points[next].dis=now.dis+edges[i].span;
                Q.push(points[next]);
            }
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int k; char st;
        scanf("%d",&k);
        edges.push_back(Ed(k));
        while((int)edges[edges.size()-1].nodetail.size()<n){
            scanf("%c",&st);
            if(st=='+'||st=='-'||st=='0')
            edges[edges.size()-1].nodetail.push_back(st);
            }
        while((int)edges[edges.size()-1].fudetail.size()<n){
            scanf("%c",&st);
            if(st=='+'||st=='-'||st=='0')
            edges[edges.size()-1].fudetail.push_back(st);
            }
    }
    for(int i=0;i<= (1<<n) -1;i++)
        points.push_back(Po(i,INF));
    
    djs();
    if(points[0].dis==INF) printf("0\n");
        else printf("%d\n",points[0].dis);
    return 0;
}

位运算+BFS，扩展时加判断，只有合法并且答案更优才加到队列里去，一直做到队列为空才输出答案。

//vijos p1019
#include <stdio.h>

#define INF 2000000000
#define STATUS 0
#define STEP 1

char function[120][20];
char condition[120][20];
int cost[120];

int answer[1<<20];
int queue[1<<20][2];
int head, tail;

void addToQueue(int status, int step){
if(answer[status] > step){
answer[status] = step;
queue[tail][STATUS] = status;
queue[tail][STEP] = step;
tail++;
}
}
int bfs(int numBug, int numPatch){
int status, step, i, j, tmp, target;
head = tail = 0;
target = (1<<numBug) - 1; //all bugs have been fixed
addToQueue(0, 0); //no bug has been fixed
while(head < tail){
status = queue[head][STATUS];
step = queue[head][STEP];
for(i=0; i<numPatch; i++){
//judge if the move is legal
tmp = 1;
for(j=0; j<numBug; j++){
switch(condition[i][j]){
case '+':
if((status>>j)&1)
tmp = 0;
break;
case '-':
if(!((status>>j)&1))
tmp = 0;
break;
}
if(tmp == 0)
break;
}
if(tmp == 0) //illegal
continue;

//move
tmp = status;
for(j=0; j<numBug; j++){
switch(function[i][j]){
case '-':
tmp |= (1<<j);
break;
case '+':
tmp &= (target^(1<<j));
break;
}
}
addToQueue(tmp, step+cost[i]);
}
head++;
}
return answer[target]==INF ? 0:answer[target];
}
int main(){
int numBug, numPatch, i;

scanf("%d %d", &numBug, &numPatch);
for(i=0; i<numPatch; i++)
scanf("%d %s %s", &cost[i], condition[i], function[i]);

for(i=0; i<(1<<numBug); i++)
answer[i] = INF;

printf("%d\n", bfs(numBug, numPatch));

return 0;
}

program asddasf;
type po=^node;
node=record
a,b:longint;
c:po;
end;
var i,j,k,l,m,n,sum:longint;
s2,s1:array[0..100] of string;
a:array[0..100] of longint;
pa:array[0..400000] of po;
dis:array[-1..400000] of longint;
h:array[0..800000] of longint;
v:array[0..400000] of boolean;
p:po;
s,s0:ansistring;
ch:boolean;
function ff(x:string):longint;
var k,l:longint;
begin
ff:=0;
l:=1;
for k:=length(x) downto 1 do
begin
if x[k]='1' then
ff:=ff+l;
l:=l*2;
end;
exit(ff);
end;

procedure chu(x1,y1:string;z1:longint);
var k,l,k1,k2:longint;
sn:ansistring;
begin
sn:=x1;
for j:=1 to n do
begin
if y1[j]='+' then
sn[j]:='1';
if y1[j]='-' then
sn[j]:='0';
end;
k1:=ff(x1);
k2:=ff(sn);
new(p);
p^.a:=k2;
p^.b:=z1;
p^.c:=pa[k1];
pa[k1]:=p;
end;
procedure sou(x,y:longint;z:string);
var j:longint;
begin
if y=n+1 then
begin
chu(z,s2[x],a[x]);
exit;
end;
if s1[x][y]='0' then
begin
sou(x,y+1,z+'1');
sou(x,y+1,z+'0');
end;
if s1[x][y]='-' then
sou(x,y+1,z+'0');
if s1[x][y]='+' then
sou(x,y+1,z+'1');
end;

procedure spfa(x:longint);
var i,j,t,u,ans:longint;
begin
fillchar(dis,sizeof(dis),$7f div 3);
dis[x]:=0;
h[1]:=x;
v[x]:=true;
t:=0; u:=1;
repeat
inc(t);
ans:=h[t];
v[ans]:=false;
p:=pa[ans];
while p<>nil do
begin
if dis[p^.a]>dis[ans]+p^.b then
begin
dis[p^.a]:=dis[ans]+p^.b;
if v[p^.a]=false then
begin
inc(u);
h[u]:=p^.a;
v[h[u]]:=true;
end;
end;
p:=p^.c;
end;
until t=u;
end;

begin
readln(n,m);
for i:=1 to m do
begin
readln(s);
j:=pos(' ',s);
s0:=copy(s,1,j-1);
val(s0,a[i]);
delete(s,1,j);
j:=pos(' ',s);
s1[i]:=copy(s,1,j-1);
delete(s,1,j);
s2[i]:=s;
end;
for i:=1 to m do
sou(i,1,'');
s:='';
for i:=1 to n do
s:=s+'1';
spfa(ff(s));
if dis[0]=dis[-1] then
writeln(0)
else
writeln(dis[0]);

end.

按照补丁个数进行BFS，先不考虑时间问题。
对每个被修复的状态剪枝——如果BFS到当前状态耗时大于被记录的最小时间，就不继续BFS。
好像数据比较弱，这样就能最多15MS过了

int bfs(){
int ret=iinf;
tmp.now=0,tmp.lv=0;
q.push(tmp);
while(!q.empty()){
tmp=q.front();
q.pop();
rep(i,0,m){
if(!( (bb2[i] == (tmp.now|bb2[i])) && (bb1[i] == (tmp.now&bb1[i])) ))
continue;

ne.now=((tmp.now&ff2[i])|ff1[i]);
ne.lv=tmp.lv+w[i];
if(vst[ne.now]&&ne.lv>=cost[ne.now])
continue;

vst[ne.now]=1;
cost[ne.now]=ne.lv;

if(ne.now==ed)
ret=ne.lv;
else
q.push(ne);
}
}
return ret;
}

高兴啊，提交了9次终于TM还是让我AC了！
测试数据 #0: Accepted, time = 0 ms, mem = 1904 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 1904 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1904 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1904 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 1908 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 1904 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 1904 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 1904 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 1908 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 1904 KiB, score = 10
Accepted, time = 60 ms, mem = 1908 KiB, score = 100

我擦，不想说了，发程序的人都TM二笔，全是编译错误

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 1264 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1264 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1260 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1268 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 1264 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 1264 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 1264 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 1264 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 1264 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 1260 KiB, score = 10
Accepted, time = 0 ms, mem = 1268 KiB, score = 100
纪念一下 思路和毒药类似 但没有构图觉得会超空间
因为有使用条件 直接枚举即可 为不构图提供了条件
BFS+位运算

点击查看程序源码+详细题解

├ 测试数据 01：答案正确... (0ms, 7260KB) 

├ 测试数据 02：答案正确... (0ms, 7260KB) 

├ 测试数据 03：答案正确... (0ms, 7260KB) 

├ 测试数据 04：答案正确... (0ms, 7260KB) 

├ 测试数据 05：答案正确... (0ms, 7260KB) 

├ 测试数据 06：答案正确... (0ms, 7260KB) 

├ 测试数据 07：答案正确... (0ms, 7260KB) 

├ 测试数据 08：答案正确... (0ms, 7260KB) 

├ 测试数据 09：答案正确... (0ms, 7260KB) 

├ 测试数据 10：答案正确... (0ms, 7260KB) 

VIJOS这碉堡了的评测机，同样的程序测了至少6遍才AC了。。。口口声声说我的0ms是TLE。。。

#01: Accepted (39ms, 504KB) 

#02: Accepted (78ms, 504KB) 

#03: Accepted (12ms, 504KB) 

#04: Accepted (16ms, 504KB) 

#05: Accepted (47ms, 504KB) 

#06: Accepted (67ms, 504KB) 

#07: Accepted (59ms, 504KB) 

#08: Accepted (153ms, 504KB) 

#09: Accepted (35ms, 508KB) 

#10: Accepted (24ms, 508KB)

编译通过... 

├ 测试数据 01：答案正确... 0ms 

├ 测试数据 02：答案正确... 0ms 

├ 测试数据 03：答案正确... 0ms 

├ 测试数据 04：答案正确... 0ms 

├ 测试数据 05：答案正确... 0ms 

├ 测试数据 06：答案正确... 0ms 

├ 测试数据 07：答案正确... 0ms 

├ 测试数据 08：答案正确... 0ms 

├ 测试数据 09：答案正确... 0ms 

├ 测试数据 10：答案正确... 0ms 

---|---|---|---|---|---|---|---|- 

Accepted 有效得分：100 有效耗时：0ms 

/*

spfa 秒过   &&   1A

用二进制表示状态，用数组记录第i个补丁是否可以用在状态j上（小优化）

 话说vijos上pascal是王道么？还是c++用着顺手。 

70行代码。spfa+位运算 

*/