PKU 1135 Domino Effect

http://poj.org/problem?id=1135
ドミノを倒していくときに、最後に倒れるドミノはどこらへんにあって、何秒で倒れるかを答えろというような問題。

倒れるドミノがキードミノの間にあるときを考えるのが若干複雑。
あと出力の文が長いです。

int n,m;
vector<PI> G[500];
int vis[500];

void solve(){
  rep(i,n)
    G[i].clear();
  
  rep(i,m){
    int a,b,l;
    cin>>a>>b>>l;
    --a,--b;
    G[a].pb(mp(b,l));
    G[b].pb(mp(a,l));
  }
  memset(vis,-1,sizeof(vis));
  priority_queue<PI> q;
  q.push(mp(0,0));
  double mc=0;
  int ans=0;
  while(!q.empty()){
    int v=q.top().S;
    int c=-q.top().F;
    q.pop();
    if(vis[v]!=-1)continue;
    vis[v]=c;
    ans=v;
    mc=c;
    FOR(it,G[v]){
      int t=it->F;
      if(vis[t]!=-1)continue;
      q.push(mp(-c-it->S,t));
    }
  }
  bool db=false;
  int aa,ab;
  rep(i,n)FOR(it,G[i]){
    int a=min(i,it->F),b=max(i,it->F);
    if(vis[a]+vis[b]+it->S>2*mc){
      db=true;
      mc=(vis[a]+vis[b]+it->S)/2.0;
      aa=a;
      ab=b;
    }
  }
  if(db)printf("The last domino falls after %.1f seconds, between key dominoes %d and %d.\n",mc,aa+1,ab+1);  
  else printf("The last domino falls after %.1f seconds, at key domino %d.\n",mc,ans+1);
}

main(){
  int sy=0;
  while(cin>>n>>m,n){
    printf("System #%d\n",++sy);
    solve();
    puts("");
  }
}