PKU 1482 It's not a Bug, It's a Feature!
http://poj.org/problem?id=1482
あるソフトウェアにバグっている場所がある。
何種類かのパッチを適用することでバグをすべて取り除くために必要な時間を求めろというような問題。
拡張ダイクストラ的な問題。
時間は結構余裕があるように思います。
int n,m; pair<int,pair<PI,PI> > ed[100]; bool vis[1<<20]; void solve(){ memset(ed,0,sizeof(ed)); memset(vis,0,sizeof(vis)); rep(i,m){ int t; string a,b; cin>>t>>a>>b; ed[i].F=t; rep(j,n){ PI& bi=ed[i].S.F; if(a[j]=='+')bi.F|=1<<j; if(a[j]=='-')bi.S|=1<<j; } rep(j,n){ PI& bi=ed[i].S.S; if(b[j]=='+')bi.F|=1<<j; if(b[j]=='-')bi.S|=1<<j; } } priority_queue<PI> q; q.push(mp(0,0)); while(!q.empty()){ int c=-q.top().F; int v=q.top().S; q.pop(); if(vis[v])continue; vis[v]=true; if(v==(1<<n)-1){ printf("Fastest sequence takes %d seconds.\n",c); return; } rep(i,m){ PI& be=ed[i].S.F; PI& af=ed[i].S.S; if((~v&be.F)!=be.F || (v&be.S)!=be.S)continue; int nv=(v|af.S)&~af.F; if(vis[nv])continue; q.push(mp(-c-ed[i].F,nv)); } } cout<<"Bugs cannot be fixed."<<endl; } main(){ int pr=0; while(cin>>n>>m,n){ printf("Product %d\n",++pr); solve(); cout<<endl; } }