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