PKU 1797 Heavy Transportation
http://poj.org/problem?id=1797
n個のノードがあって、あるノードからあるノードに道があるとき、その道は最大で重さwまで通ることが出来る。
ノード1からノードnまで運べる最大の重量はいくらかを求めろという問題。
vectorやqueueを使って、重さを所持してBFSするとTLEだったのでいろいろと高速化をした。queueのサイズを見誤って何回かWAを頂いた。
const int MAX=(1<<18)-1; int we[1000]; PI G[1000][1000]; int Gs[1000]; PI Q[MAX+1]; int s,num; main(){ int sc; scanf("%d",&sc); rep(ssc,sc){ cout<<"Scenario #"<<ssc+1<<':'<<endl; int n,m; scanf("%d%d",&n,&m); fill(we,we+n,0); rep(i,n)Gs[i]=0; rep(i,m){ int a,b,w; scanf("%d%d%d",&a,&b,&w); --a,--b; G[a][Gs[a]++]=mp(b,w); G[b][Gs[b]++]=mp(a,w); } s=num=0; Q[s+num++]=mp(10000000,0); while(num){ int cw=Q[s&MAX].F,v=Q[s&MAX].S; ++s,--num; if(we[v]>=cw)continue; we[v]=cw; rep(i,Gs[v]){ int nw=min(cw,G[v][i].S),to=G[v][i].F; if(we[to]>=nw)continue; Q[s+num++&MAX]=mp(nw,to); } } cout<<we[n-1]<<endl<<endl; } }