题目是 poj - 2728。

通过的 sol 如下：

#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const double eps=1e-8;
const int INF=0x3f3f3f3f;
struct point {
	int x,y,w;
} pnt[1100];
int n,vis[1100]; double tmp[1100],dis[1100][1100];
inline double Dis(const point u,const point v) { return sqrt(pow(u.x-v.x,2)+pow(u.y-v.y,2)); }
inline double f(const int x,const int y,double coef) { return abs(pnt[x].w-pnt[y].w)-coef*dis[x][y]; }
inline bool Check(const double cur) {
	for(int i=1; i<=n; ++i)	vis[i]=0,tmp[i]=f(1,i,cur);
	double res=0; vis[1]=1;
	for(int i=1; i<=n; ++i) {
		double tt=INF; int pos;
		for(int j=1; j<=n; ++j)	if(!vis[j] && tmp[j]<tt)	tt=tmp[j],pos=j;
		if(tt==INF)	break;
		res+=tt; vis[pos]=1;
		for(int j=1; j<=n; ++j) {
			if(!vis[j] && tmp[j]>f(pos,j,cur))	tmp[j]=f(pos,j,cur);
		}
	}
	return res>eps;
}
char buf[1<<21],*p1=buf,*p2=buf;
#define Gc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int Getint() {
	int x=0; char c=Gc(); bool f=0;
	while(c<'0' || c>'9')	f|=(c=='-'),c=Gc();
	while(c>='0' && c<='9')	x=x*10+(c&15),c=Gc();
	return f?-x:x;
}
signed main() {
	while(n=Getint()) {
		for(int i=1; i<=n; ++i)	pnt[i]=(point){Getint(),Getint(),Getint()};
		for(int i=1; i<=n; ++i) {
			for(int j=1; j<=n; ++j)	dis[i][j]=Dis(pnt[i],pnt[j]);
		}
		double l=0,r=1e9;
		while(l+eps<r) {
			double mid=(l+r)/2;
			if(Check(mid))	l=mid;
			else	r=mid;
		}
		printf("%.3f\n",l);
	}
	return 0;
}

被卡常的代码是：

#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const double eps=1e-8;
const int INF=0x3f3f3f3f;
struct point {
	int x,y,w;
} pnt[1100];
int n,vis[1100]; double tmp[1100],dis[1100][1100];
inline double Dis(const point u,const point v) { return sqrt(pow(u.x-v.x,2)+pow(u.y-v.y,2)); }
inline double f(const int x,const int y,double coef) { return abs(pnt[x].w-pnt[y].w)-coef*dis[x][y]; }
inline bool Check(const double cur) {
	for(int i=1; i<=n; ++i)	vis[i]=0,tmp[i]=f(i,1,cur);
	double res=0; vis[1]=1;
	for(int i=1; i<=n; ++i) {
		double tt=INF; int pos;
		for(int j=1; j<=n; ++j)	if(!vis[j] && tmp[j]<tt)	tt=tmp[j],pos=j;
		if(tt==INF)	break;
		res+=tt; vis[pos]=1;
		for(int j=1; j<=n; ++j) {
			if(!vis[j] && tmp[j]>f(j,pos,cur))	tmp[j]=f(j,pos,cur);
		}
	}
	return res>eps;
}
char buf[1<<21],*p1=buf,*p2=buf;
#define Gc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int Getint() {
	int x=0; char c=Gc(); bool f=0;
	while(c<'0' || c>'9')	f|=(c=='-'),c=Gc();
	while(c>='0' && c<='9')	x=x*10+(c&15),c=Gc();
	return f?-x:x;
}
signed main() {
	while(n=Getint()) {
		for(int i=1; i<=n; ++i)	pnt[i]=(point){Getint(),Getint(),Getint()};
		for(int i=1; i<=n; ++i) {
			for(int j=1; j<=n; ++j)	dis[i][j]=Dis(pnt[i],pnt[j]);
		}
		double l=0,r=1e9;
		while(l+eps<r) {
			double mid=(l+r)/2;
			if(Check(mid))	l=mid;
			else	r=mid;
		}
		printf("%.3f\n",l);
	}
	return 0;
}

唯一的区别在于：

for(int i=1; i<=n; ++i)	vis[i]=0,tmp[i]=f(1,i,cur);
v.s.
for(int i=1; i<=n; ++i)	vis[i]=0,tmp[i]=f(i,1,cur);

if(!vis[j] && tmp[j]>f(pos,j,cur))	tmp[j]=f(pos,j,cur);
v.s.
if(!vis[j] && tmp[j]>f(j,pos,cur))	tmp[j]=f(j,pos,cur);

求问这个常数是怎么来的，如果是 cache 或者其他的原因敬请告知。