PKU 3255 Roadblocks
http://poj.org/problem?id=3255
長さが2番目の経路を出力するという問題。
500問目。
蟻本のを参考にして、適当に書いてみました。
vector<PI> G[5000]; set<int> dis[5000]; main(){ int n,r; cin>>n>>r; rep(i,r){ int a,b,c; cin>>a>>b>>c; --a,--b; G[a].pb(mp(b,c)); G[b].pb(mp(a,c)); } priority_queue<PI> q; q.push(mp(0,0)); while(!q.empty()){ int c=-q.top().F,v=q.top().S;q.pop(); if(dis[v].size()>1 || dis[v].count(c))continue; dis[v].insert(c); if(dis[v].size()==2 && v==n-1){ cout<<c<<endl; break; } rep(i,SZ(G[v])){ int to=G[v][i].F; int nc=c+G[v][i].S; if(dis[to].size()>1)continue; q.push(mp(-nc,to)); } } }