PKU : 3268 - Silver Cow Party - Respect2Dの日記

問題概要

有向グラフが与えられる.
各ノードからノードXまで行って帰るまでの最短距離の, 最大値を出力せよ.

アルゴリズム

ワーシャルフロイドで書きたくなりますが, 1000^3のオーダがかかって無理でしょう.
単一始点最短距離を求めるダイクストラであれば, オーダは余裕そうです.
ノードXから, 全てのノードに帰っていく最短路は, ノードXからのダイクストラになります.
逆に, 行きの最短路はというと, グラフのエッジを全て逆向きにして, ノードXからダイクストラをすれば求めることができます.

プログラム

typedef pair<int,int> P;

void dijk(int x,int *dist,vector<P> *t){
  priority_queue<P,vector<P>,greater<P> > open;
  open.push(P(0,x));

  while(!open.empty()){
    P p = open.top(); open.pop();
    if(dist[p.second] != -1) continue;

    dist[p.second] = p.first;

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

int main(void){
  int n,m,x;
  int a,b,cost;
  vector<P> t[1002];
  vector<P> rt[1002];
  scanf("%d%d%d",&n,&m,&x);
  x--;

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

  int to[1002];
  int back[1002];
  memset(to,-1,sizeof(to));
  memset(back,-1,sizeof(back));

  dijk(x,to,rt);
  dijk(x,back,t);

  int ans = 0;
  rep(i,n){
    ans = max(ans,to[i]+back[i]);
  }

  printf("%d\n",ans);
}