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