题面
BZOJ https://lydsy.com/JudgeOnline/problem.php?id=5471
洛谷 https://www.luogu.org/problemnew/show/P4579
给定平面上若干个点, 保证这些点在两条平行线上, 给定起点终点, 求从起点出发, 遍历所有点后到达终点的最短路径长度.
题解
不会做, 于是点开 LOJ, 点开除了 \(std\) 之外唯一过的人的代码 https://loj.ac/submission/351572 , 照着打了一遍 QwQ......
然后再对着代码 YY 一遍就有了这篇东西......
强制令起点的位置是第 \(0\) 行 (方便而已).
在第 \(0\) 行枚举一个 \(i\), 在第一行枚举一个 \(j\).
设 \(f[j][0]\) 表示第 \(1\) 行 \([j+1,n_1]\) 这些点已经走完, 第 \(0\) 行 \([i,n_0]\) 已经走完, 然后到达终点的最短路.
设 \(f[j][1]\) 表示第 \(1\) 行 \([j,n_1]\) 已经走完, 第 \(0\) 行 \([i+1,n_0]\) 已经走完, 然后达到终点的最短路.
把 \(i\) 按照从前往后或者从后往前的顺序枚举, 到达起点就直接更新答案.
因为从起点出发可以向两个方向走, 所以前后都要做一遍 \(dp\).
转移的话就是一堆讨论.
- #include<iostream>
- #include<cstdio>
- #include<cmath>
- #include<algorithm>
- using namespace std;
- #define MAX 10100
- inline int read()
- {
- int x=0;bool t=false;char ch=getchar();
- while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
- if(ch=='-')t=true,ch=getchar();
- while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
- return t?-x:x;
- }
- int n[2],ty[2],pos[2];
- double h,tx[2],x[2][MAX],f[MAX][2];
- double Dis(int i,int j)
- {
- double d=fabs(x[0][i]-x[1][j]);
- return sqrt(d*d+h*h);
- }
- double ToEnd(int i,int j)
- {
- double d=fabs(x[i][j]-tx[1]);
- return i==ty[1]?d:sqrt(h*h+d*d);
- }
- double Calc()
- {
- double ret=1e18;
- sort(&x[0][1],&x[0][n[0]+1]);
- sort(&x[1][1],&x[1][n[1]+1]);
- for(int i=n[0];i;--i)
- {
- if(i==n[0])
- for(int j=n[1];j;--j)
- {
- f[j][0]=j==n[1]?ToEnd(0,n[0]):min(f[j+1][1]+Dis(n[0],j+1),Dis(n[0],n[1])+x[1][n[1]]-x[1][j+1]+ToEnd(1,j+1));
- f[j][1]=j==n[1]?ToEnd(1,n[1]):f[j+1][1]+x[1][j+1]-x[1][j];
- }
- else
- for(int j=n[1];j;--j)
- if(j==n[1])
- {
- f[j][1]=min(f[j][0]+Dis(i+1,j),Dis(n[0],n[1])+x[0][n[0]]-x[0][i+1]+ToEnd(0,i+1));
- f[j][0]+=x[0][i+1]-x[0][i];
- }
- else
- {
- f[j][1]=min(f[j][0]+Dis(i+1,j),f[j+1][1]+x[1][j+1]-x[1][j]);
- f[j][0]=min(f[j][0]+x[0][i+1]-x[0][i],f[j+1][1]+Dis(i,j+1));
- }
- ret=min(ret,x[0][i]-x[0][1]+tx[0]-x[0][1]+Dis(i,1)+f[1][1]);
- ret=min(ret,fabs(x[0][i]-tx[0])+x[0][i]-x[0][1]+Dis(1,1)+f[1][1]);
- if(x[0][i]<=tx[0])
- {
- ret=min(ret,tx[0]-x[0][1]+Dis(1,1)+f[1][1]);
- break;
- }
- }
- return ret;
- }
- int main()
- {
- scanf("%d%d%d%d%d%d%lf",&n[0],&n[1],&ty[0],&pos[0],&ty[1],&pos[1],&h);
- int r=0;if(ty[0])r=1,swap(n[0],n[1]),ty[0]^=1,ty[1]^=1;
- for(int t=0;t<=1;++t)
- for(int i=1;i<=n[t^r];++i)
- scanf("%lf",&x[t^r][i]);
- tx[0]=x[ty[0]][pos[0]];
- tx[1]=x[ty[1]][pos[1]];
- double ans=Calc();
- for(int t=0;t<=1;++t)
- for(int i=1;i<=n[t];++i)
- x[t][i]=20000-x[t][i];
- tx[0]=20000-tx[0];tx[1]=20000-tx[1];
- ans=min(ans,Calc());
- printf("%.2lf\n",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2970584.html