PKU 3767 I Wanna Go Home
http://poj.org/problem?id=3767
街1から街2へ移動したい。街は全部でn個あり、それぞれの街は、二人の指導者のうちどちらかを支持している。安全のために、支持者が違う街同士の移動を、多くとも一回で済ませられるような最短の経路を求めろというような問題。
pop()の位置を変なところに入れていて、それがTLEの原因だと気づかずに、無駄に高速化してました。
よく考えると、pair
PI G[600][600]; int Gs[600]; int le[600]; bool vis[600]; main(){ int n,m; while(scanf("%d",&n),n){ scanf("%d",&m); memset(Gs,0,sizeof(Gs)); rep(i,m){ int a,b,t; scanf("%d%d%d",&a,&b,&t); --a,--b; G[a][Gs[a]++]=mp(b,t); G[b][Gs[b]++]=mp(a,t); } rep(i,n)scanf("%d",le+i); int ans=-1; priority_queue<pair<int,PI> > q; memset(vis,0,sizeof(vis)); q.push(mp(0,mp(0,0))); while(!q.empty()){ int cc=-q.top().F,v=q.top().S.F,cl=q.top().S.S; q.pop(); if(vis[v])continue; vis[v]=true; if(v==1){ ans=cc; break; } rep(i,Gs[v]){ int to=G[v][i].F; if(cl==2 && le[to]==1)continue; if(vis[to])continue; q.push(mp(-cc-G[v][i].S,mp(to,le[to]))); } } printf("%d\n",ans); } }