简单的dp，O(nlogn+mlogm+n*m)

解题思路:见注释

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

#define maxm 2010

#define maxn 2010

typedef long long ll;

int n,m;

ll d;

ll a[maxn],b[maxm];

double dp[maxn][maxm][2];

//dp[i][j][0]是上面已经走了i个点，下面已经走了j个点，当前在上面

//对应的最小路程

//dp[i][j][1]是上面已经走了i个点，下面已经走了j个点，当前在下面

//对应的最小路程

int main(){

scanf("%d%d%lld",&n,&m,&d);

for(int i=1;i<=n;i++)scanf("%lld",&a[i]);

for(int i=1;i<=m;i++)scanf("%lld",&b[i]);

sort(a+1,a+1+n);

sort(b+1,b+1+m);

for(int i=0;i<=n;i++){

for(int j=0;j<=m;j++){

dp[i][j][0]=1e9;

dp[i][j][1]=1e9;

}

}

dp[0][0][0]=0;

dp[0][0][1]=0;

for(int i=1;i<=n;i++){

dp[i][0][0]=a[i];

}

for(int j=1;j<=m;j++){

dp[0][j][1]=d+b[j];

}

for(int i=1;i<=n;i++){

for(int j=1;j<=m;j++){

dp[i][j][0]=min(dp[i-1][j][0]+a[i]-a[i-1],

dp[i-1][j][1]+sqrt(1.0*d*d+(a[i]-b[j])*(a[i]-b[j])));

dp[i][j][1]=min(dp[i][j-1][1]+b[j]-b[j-1],

dp[i][j-1][0]+sqrt(1.0*d*d+(a[i]-b[j])*(a[i]-b[j])));

}

} 

printf("%.2lf",min(dp[n][m][0],dp[n][m][1]));

return 0;

}