提出 #46561

---

ソースコード 拡げる

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <iomanip>
using namespace std;
static const double EPS = 1e-5;
typedef long long ll;

double c[1001][1001];
double ans[1001];
int main() {

	int N;
	cin>>N;

	if(N==1){
		cout<<0<<endl;
		return 0;
	}
	vector <int> uv;
	vector <int> x,y,r,t;
	for(int i=0;i<N;++i){
		int tmpx,tmpy;
		cin>>tmpx>>tmpy;
		x.push_back(tmpx);
		y.push_back(tmpy);
		cin>>tmpx>>tmpy;
		t.push_back(tmpx);
		r.push_back(tmpy);
		if(i!=0)uv.push_back(i);
	}

	for(int i=0;i<N;++i){
		for(int j=0;j<N;++j){
			c[i][j]= sqrt(abs(x[i]-x[j])*abs(x[i]-x[j])
				+ abs(y[i]-y[j])*abs(y[i]-y[j]))/(double)min(t[i],r[j]);
		}
			ans[i]=-1;
	}


	vector <int> v;
	v.push_back(0);
	ans[0]=0;
	while(1){
		double neigh=1000000;
		int from=0,to=0;
		for(int i=0;i<v.size();++i){
			for(int j=0;j<uv.size();++j){
				if(ans[v[i]]>=0&&neigh> ans[v[i]]+c[v[i]][uv[j]]){
					neigh=ans[v[i]]+c[v[i]][uv[j]];
					from=i;
					to=uv[j];
				}
			}
		}
		ans[to]=neigh;
		v.push_back(to);
		uv.erase(remove(uv.begin(),uv.end(),to),uv.end());
		if(uv.size()==0)break;
	}

	double result=0;
	vector <double> res;
	for(int i=0;i<N;++i){
		res.push_back(ans[i]);
	}
	sort(res.begin(),res.end());


	for(int i=0;i<N-1;++i){
		result=(res[N-i-1]+(double)i>result)?res[N-i-1]+(double)i:result;
	}
cout<<setprecision(10);	cout<<result<<endl;
}

提出情報

ジャッジ結果