评测状态 Accepted
题目 P1014 旅行商简化版
递交时间 2015-08-20 20:09:06
代码语言 C++
评测机 Jtwd2
消耗时间 308 ms
消耗内存 16180 KiB
评测时间 2015-08-20 20:09:07
评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 16176 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 16176 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 16180 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 16168 KiB, score = 10
测试数据 #4: Accepted, time = 31 ms, mem = 16176 KiB, score = 10
测试数据 #5: Accepted, time = 46 ms, mem = 16176 KiB, score = 10
测试数据 #6: Accepted, time = 62 ms, mem = 16176 KiB, score = 10
测试数据 #7: Accepted, time = 46 ms, mem = 16172 KiB, score = 10
测试数据 #8: Accepted, time = 62 ms, mem = 16168 KiB, score = 10
测试数据 #9: Accepted, time = 46 ms, mem = 16172 KiB, score = 10
Accepted, time = 308 ms, mem = 16180 KiB, score = 100
代码
#include<iostream>
#include<math.h>
#include<stdio.h>
using namespace std;
int n;
double f[1001][1001];
double d[1001][1001];
double x[1001],y[1001];
void Qsort(int left,int right)
{
if(left>=right) return ;
int i=left,j=right;double mid=x[(left+right)>>1];
while(i<=j)
{
while(x[i]<mid) i++;
while(x[j]>mid) j--;
if(i<=j)
{
swap(x[i],x[j]);
swap(y[i],y[j]);
i++;j--;
}
}
Qsort(left,j);
Qsort(i,right);
}
int main()
{
cin>>n;
for(int i=1;i<=n;++i)
cin>>x[i]>>y[i];
Qsort(1,n);
for(int i=1;i<=n;++i)
for(int j=i+1;j<=n;++j)
d[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
f[i][j]=1e24;
f[2][1]=d[1][2];
for(int i=3;i<=n;i++)
for(int j=1;j<i;j++)
if(j<i-1) f[i][j]=f[i-1][j]+d[i-1][i];
else
{
for(int k=1;k<j;++k)
f[i][j]=min(f[i][j],f[j][k]+d[k][i]);

}

printf("%.2lf\n",f[n][n-1]+d[n-1][n]);
return 0;
｝