PKU 2457 Part Acquisition
http://poj.org/problem?id=2457
物々交換でアイテム1をアイテムkに変換するまでの最短経路を出力するというような問題。
アイテムkに到達できないときに-1を返すというの見落としてMLEだしまくりました。
BFS+経路復元
vector<int> G[1001]; int ba[1001]; bool qin[1001]; main(){ int n,k; scanf("%d%d",&n,&k); rep(i,n){ int a,b; scanf("%d%d",&a,&b); G[a].pb(b); } queue<PI>q; q.push(mp(1,1)); while(!q.empty()){ PI v=q.front(); q.pop(); if(ba[v.F])continue; ba[v.F]=v.S; if(v.F==k)break; rep(i,SZ(G[v.F])){ if(qin[G[v.F][i]])continue; if(ba[G[v.F][i]])continue; q.push(mp(G[v.F][i],v.F)); qin[G[v.F][i]]=true; } } vector<int>ans; int item=k; while(true){ ans.pb(item); if(item==1)break; item=ba[item]; if(item==0){ cout<<-1<<endl; return 0; } } reverse(ALL(ans)); cout<<SZ(ans)<<endl; FOR(iter,ans)cout<<*iter<<endl; }