【题意】

有n + 1个点,其中n个点都在数轴x轴上。
求最短的从第k个点开始的哈密尔顿路。
n ≤ 10 

【解题方法】

题解描述来自xhr大牛的论文

先对x轴上的点按x坐标排序,设排序后为a 1 ...a n . 设x轴外的点为p
如果人正好在那个x轴外的点,可以证明最优解是 dist(a 1 ,a n )+min(dist(a 1 ,p),dist(a n ,p))
否则,可以证明:
一定存在x轴上某点k,使得人先走遍1~k,回来,再走遍k + 1~n;或者先走遍k +
1~n,回来,再走遍1~k.
于是我们考虑2个情况:
• 从点p出发,走一个区间 l ,r。 最佳方案显然是从p到l或r中较近的一个,然后一路走到
对面。 距离是dist(a l ,a r ) + min(dist(p,a l ),dist(p,a r ))
• 从点k出发,走一个区间 l ,r,再回到p。 最佳方案可以证明是从k走到l或r中的某一个,
然后走到对面,然后走到p。 距离是abs(a l − a r ) + min(abs(a k − a l ) + dist(r),abs(a k − a r ) +
dist(l))
枚举k,我们可以O(1)计算出答案。取最优值。 O(N)

【AC代码】


//
//Created by just_sort 2016/12/20
//Copyright (c) 2016 just_sort.All Rights Reserved
//

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream> //isstringstream
#include <iostream>
#include <algorithm>
using namespace std;
using namespace __gnu_pbds;
typedef long long LL;
//typedef pair<int, LL> pp;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPZ(i, n) for(int i = 1; i <= n; i++)
#define MP(x,y) make_pair(x,y)
const int maxn = 100020;
const int maxm = 1<<12;
const int inf = 1e9;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>order_set;
//head
int N, x[100010], y;
double a[100010], b[100010];
double getdis(double x, double y){
    return sqrt(x*x + y*y);
}
double cal(int l, int r, int k){
    double d1 = getdis(x[N] - x[l], y);
    double d2 = getdis(x[N] - x[r], y);
    if(k >= l && k <= r){
        return x[r] - x[l] + min(x[r] - x[k] + d1, x[k] - x[l] + d2);
    }
    else{
        return x[r] - x[l] + min(d1, d2);
    }
}
int main()
{
    int K2, K;
    scanf("%d%d",&N,&K2);K2--;
    for(int i = 0; i < N + 1; i++) scanf("%d", &x[i]); scanf("%d", &y);
    int sx = x[K2];
    sort(x, x + N);
    if(K2 == N){
        K = N;
    }
    else{
        for(int i = 0; i < N; i++){
            if(x[i] == sx){
                K = i;
                break;
            }
        }
    }
    for(int i  = 1; i <= N; i++){
        a[i] = cal(0, i-1, K);
    }
    for(int i = 0; i < N; i++){
        b[i] = cal(i, N-1, K);
    }
    double ans = 1e9;
    if(K == N){
        ans = a[N];
    }
    else{
        for(int i = 0; i < N + 1; i++){
            ans = min(ans, a[i] + b[i]);
        }
    }
    printf("%.9f\n", ans);
    return 0;
}