PKU 2607 Fire Station
http://poj.org/problem?id=2607
i個のノードを持つ無向グラフがある。このうちf個のノードについて消防署が立っている。
もう一つ消防署を建てることを考えた時、それぞれのノードからどれかの消防署までの最短距離のうち、その最大値が最も短くなるもので、ノード番号が最小のものを答えろというような問題。
愚直すぎないワーシャルフロイドで通るっぽいです。
1秒切っている人たちはよくわかりません。
int wall[500][500]; int fire[100]; int near[500]; main(){ int f,n; scanf("%d%d",&f,&n); rep(i,f){ scanf("%d",fire+i); --fire[i]; } rep(i,n){ rep(j,n)wall[i][j]=1<<29; wall[i][i]=0; near[i]=1<<29; } int a,b,c; while(~scanf("%d%d%d",&a,&b,&c)){ --a,--b; wall[a][b]=wall[b][a]=min(wall[a][b],c); } rep(k,n)rep(i,n)rep(j,i)wall[j][i]=wall[i][j]=min(wall[i][j],wall[i][k]+wall[k][j]); int mind=1<<29; int ans; rep(i,n)rep(j,f){ near[i]=min(near[i],wall[i][fire[j]]); } rep(i,n){ int tmind=0; rep(j,n)tmind=max(tmind,min(near[j],wall[j][i])); if(tmind<mind){ ans=i; mind=tmind; } } printf("%d\n",ans+1); }