18.03.26 vijos1069新年趣事之红包

本文主要是介绍18.03.26 vijos1069新年趣事之红包，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

描述

xiaomengxian一进门，发现外公、外婆、叔叔、阿姨……都坐在客厅里等着他呢。经过仔细观察，xiaomengxian发现他们所有人正好组成了一个凸多边形。最重要的是，他们每个人手里都拿着一个红包（^o^）。于是非常心急，xiaomengxian决定找一条最短的路线，拿到所有的红包。

假设屋里共有N个人拿着红包，把他们分别从1到N编号。其中，编号为1的人就坐在大门口，xiaomengxian必须从这里出发去拿其它的红包。一条合法的路线必须经过所有的点一次且仅一次。

格式

输入格式

第一行为一个整数N（1<=N<=800）。

以下N行，每行两个实数Xi，Yi，表示该点的坐标。

各个点按照逆时针顺序依次给出。

输出格式

一个实数，表示最短的路线长度（保留三位小数）。

样例1

样例输入1

4
50.0 1.0
5.0 1.0
0.0 0.0
45.0 0.0

样例输出1

50.211

限制

各个测试点1s

来源

Xiaomengxian

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstdio>
 4 #include <stdlib.h>
 5 #include <math.h>
 6 
 7 using namespace std;
 8 
 9 const int maxn=1000;
10 int n;
11 double dis[maxn][maxn];
12 
13 struct node{
14     double x,y;
15 }p[maxn];
16 
17 double f[maxn][maxn][2];//编号；经过几个点；分两个数组分别存放由第一个点到第二个点（遍历之间的所有点）的最短路径和第二个点到第一个点的最短路径
18 
19 void init(){
20     scanf("%d",&n);
21     for(int i=0;i<=n-1;i++)
22         scanf("%lf%lf",&p[i].x,&p[i].y);
23 }
24 double distan(node a,node b){
25     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
26 }
27 
28 int main()
29 {
30     double ans=99999999;
31     init();
32     for(int i=0;i<=n-1;i++)
33         for(int j=0;j<=n-1;j++){
34         dis[i][j]=distan(p[i],p[j]);
35     }
36     for(int i=2;i<=n;i++)
37         for(int j=0;j<=n-1;j++){
38             f[j][i][1]=min(f[j][i-1][0]+dis[j][(j+i-1)%n],f[j][i-1][1]+dis[(j+i-1)%n][j]);
39             f[j][i][0]=min(f[(j+1)%n][i-1][0]+dis[j][(j+1)%n],f[(j+1)%n][i-1][1]+dis[j][(j+i-1)%n]);
40         }
41     for(int i=0;i<=n-1;i++)
42         ans=min(f[i][n][0],ans);
43     printf("%.3lf\n",ans);
44     return 0;
45 }