PKU 1465 Multiple
http://poj.org/problem?id=1465
m個の1桁の数字を並べてnの倍数で最小の正の整数を作れという問題。
余りをノードとするグラフ上で幅優先探索+経路復元。
do-while文の終了条件が間違っていることに気が付かなくてサンプルがなかなか通せませんでした。
あと、最初dfsでやっていたら、全然間に合いませんでした。
int n,m; char out[10000]; int sz; int in[100]; PI vis[10000]; main(){ while(cin>>n>>m){ rep(i,m)cin>>in[i]; if(!n){ cout<<0<<endl; continue; } sort(in,in+m); queue<pair<PI,PI> > q; q.push(mp(mp(0,0),mp(0,0))); memset(vis,-1,sizeof(vis)); bool ok=false; while(!q.empty()){ int le=q.front().F.F; int ben=q.front().F.S; int rem=q.front().S.F; int be=q.front().S.S; q.pop(); if(vis[rem].F!=-1)continue; if(le)vis[rem]=mp(be,ben); if(le && rem==0){ ok=true; break; } for(int i=(le==0 && in[0]==0);i<m;++i) q.push(mp(mp(le+1,in[i]),mp((rem*10+in[i])%n,rem))); } if(!ok){ cout<<0<<endl; continue; } int rem=0; bool n0=false; sz=0; do{ out[sz++]=vis[rem].S+'0'; n0|=vis[rem].S; out[sz]=0; rem=vis[rem].F; }while(rem || !n0); reverse(out,out+sz); puts(out); } }