PKU : 3255 - Roadblocks

問題概要

http://poj.org/problem?id=3255

双方向グラフが与えられます.
ノード１とノードNの間の2番目に短い距離を求めよ.

アルゴリズム

基本的にはダイクストラ法で解けます.
ただし, 今回は2番目の最短路なので, いつも bool closed[5002] としているところを, int closed[5002] として, closed が2以上のときは分岐しないようにしました.

プログラム

typedef pair<int,int> P;

int main(void){
  int n,r;
  vector<P> t[5002];
  scanf("%d%d",&n,&r);

  rep(i,r){
    int a,b,cost;
    scanf("%d%d%d",&a,&b,&cost);
    a--;
    b--;
    t[a].push_back(P(b,cost));
    t[b].push_back(P(a,cost));
  }

  priority_queue<P,vector<P>,greater<P> > open;
  int closed[5002],dist[5002];
  bool firstFlg = false;
  memset(closed,0,sizeof(closed));
  memset(dist,-1,sizeof(dist));
  open.push(P(0,0));

  while(!open.empty()){
    P p = open.top(); open.pop();
    if(closed[p.second] >= 2 || dist[p.second] == p.first) continue;
    closed[p.second]++;
    dist[p.second] = p.first;

    if(p.second == n-1){
      if(firstFlg){
        printf("%d\n",p.first);
        break;
      }
      firstFlg = true;
    }

    rep(i,t[p.second].size()){
      P next = t[p.second][i];
      open.push(P(p.first+next.second,next.first));
    }
  }
}