记录编号	391095	评测结果	AAAAAAAAAA
题目名称	线型网络	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	1.301 s
提交时间	2017-04-05 09:02:47	内存使用	160.29 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <list>
#include <vector>
using namespace std;
double dist[20][20];
double f[20][1<<20];
int x[20], y[20];
int main(){
  freopen("linec.in", "r", stdin);
  freopen("linec.out", "w", stdout);
  int n; scanf("%d", &n);
  for(int i = 0; i < n; i++)scanf("%d %d", x+i, y+i);
  for(int i = 0; i < n; i++)for(int j = i+1; j < n; j++)
    dist[i][j] = dist[j][i] = sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
  double ans = 1e10;
  int s = (1<<n)-1;
  for(int i = 0; i < n; i++)fill(f[i], f[i]+(1<<n), 1e10);
  for(int i = 0; i < n; i++)f[i][1<<i] = 0;
  for(int s0 = 1; s0 <= s; s0++)for(int i = 0; i < n; i++)if(s0 & (1<<i)){
    for(int j = 0; j < n; j++)if(!(s0 & (1<<j)))
      f[j][s0|(1<<j)] = min(f[j][s0|(1<<j)], f[i][s0]+dist[i][j]);
  }
  for(int i = 0; i < n; i++)ans = min(ans, f[i][s]);
  printf("%.2lf\n", ans);
  return 0;
}