poj2728 Desert King

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include <algorithm>
using namespace std;
const int N=1007;
const double eps=1e-6;
struct city{
    int x,y,v;
}c[N];
double rr[N][N],cost[N][N],a[N][N],mid,d[N],ans,l,r;
int n;
bool v[N];
double len(int x,int y){
    return sqrt((c[x].x-c[y].x)*(c[x].x-c[y].x)+(c[x].y-c[y].y)*(c[x].y-c[y].y));
}
int main(){
    //freopen("in","r",stdin);
    //freopen("out.out","w",stdout);
    while(1){
        double num=0.0;
        scanf("%d",&n);
        if(n==0)break;
        for(int i=1;i<=n;i++){
            scanf("%d%d%d",&c[i].x,&c[i].y,&c[i].v);
        }
        for(int i=1;i<=n;i++)
            for(int j=i;j<=n;j++){
                rr[j][i]=rr[i][j]=len(i,j);
                num+=(cost[i][j]=cost[j][i]=abs(c[i].v-c[j].v));
            }
        l=0.0,r=100;
        while(l+eps<=r){
            mid=(l+r)/2;
            ans=0;
            for(int i=1;i<=n;i++)
                for(int j=i;j<=n;j++){
                    if(i==j)a[i][j]=0x3f3f3f3f;
                    else a[i][j]=a[j][i]=cost[i][j]-mid*rr[i][j];
                }
            for (int i = 1; i <= n; i++) d[i] =0x3f3f3f3f;
                memset(v,0,sizeof(v));
                d[1]=0;
                while(1){
                    int x=0;
                    for(int j=1;j<=n;j++)
                        if(!v[j]&&(x==0||d[j]<d[x]))x=j;
                    if(!x)break;
                    v[x]=1;
                    ans+=d[x];
                    for(int y=1;y<=n;y++)
                        d[y]=min(d[y],a[x][y]);
                }
            if(ans>=0)l=mid;
            else r=mid;
        }
        printf("%.3f\n",l);
    }
    return 0;
}