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;
  }
}