PKU 2253 Frogger
http://poj.org/problem?id=2253
n個の石の座標が与えられる。このとき、石1から石2まで、いくつかの石をジャンプして行っても良い時、経由する石と石の距離の最大値の最小値を求めるというような問題。
辺の長さが短い順に追加していき、union-findで管理する。
int un[200]; int find(int x){ if(x==un[x])return x; return un[x]=find(un[x]); } int unit(int a,int b){ un[find(a)]=un[find(b)]=find(a); } int x[200],y[200]; main(){ int n; int sc=0; while(cin>>n,n){ ++sc; cout<<"Scenario #"<<sc<<endl; rep(i,n){ cin>>x[i]>>y[i]; un[i]=i; } priority_queue<pair<int,PI> > Q; rep(i,n){ rep(j,i){ int d=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]); Q.push(mp(-d,mp(i,j))); } } while(true){ int cc=-Q.top().F,a=Q.top().S.F,b=Q.top().S.S; Q.pop(); if(find(a)==find(b))continue; unit(a,b); if(find(0)==find(1)){ printf("Frog Distance = %.3f\n\n",sqrt(cc)); break; } } } }