Description
给你起点和终点的三维坐标 $(s_x,s_y,s_z)$ 和 $(e_x,e_y,e_z)$ ，以及 $n$ 个球的球心的三维坐标 $(x_i,y_i,z_i)$ 和星域的半径 $r_i$ 。现在要从起点到终点，在一个球内穿梭不需要时间，你的速度是 $0.1$ ，现在请你求出从起点到终点所需的最短时间，结果取整到最近的整数，输入数据保证取整是明确的。
$0 \leq n \leq 100,0 \leq |x_i|,|y_i|,|z_i|,r_i\leq 10^4$ 。
Solution
考虑使用 Floyd 来解题。
把起点和终点也当做一个半径为 的球来存，然后给任意两点之间先建一条边。
考虑两个球之间的最短路，可以得出为两个圆心之间的距离减去两个球的半径，即：
$\sqrt{(z_i-z_j)^2+(x_i-x_j)^2+(y_i-y_j)^2}-r_i-r_j$。
然后就很舒服了，直接套一个 Floyd 即可。
时间复杂度 O(n^3) ，具体细节详见 代码 部分。
然后这道题目就做完了。
Code
1 | #include<map>
|
2 | #include<queue>
|
3 | #include<cmath>
|
4 | #include<cstdio>
|
5 | #include<vector>
|
6 | #include<string>
|
7 | #include<cstring>
|
8 | #include<iostream>
|
9 | #include<algorithm>
|
10 | using namespace std;
|
11 | int n,x[101],y[101],z[101],r[101],t;
|
12 | double sx,sy,sz,ex,ey,ez;
|
13 | double nx,ny,nz,dx,dy,dz;
|
14 | double ma[103][103];
|
15 | double abss(double x){return x>(-x)?x:(-x);}
|
16 | double minn(double x,double y){return x<y?x:y;}
|
17 | int main()
|
18 | {
|
19 | freopen("warp.in","r",stdin);
|
20 | freopen("warp.out","w",stdout);
|
21 | cin>>n;
|
22 | while(n!=-1)
|
23 | {
|
24 | for(int i=1;i<=n;i++)
|
25 | cin>>x[i]>>y[i]>>z[i]>>r[i];
|
26 | cin>>sx>>sy>>sz>>ex>>ey>>ez;
|
27 | x[++n]=sx;y[n]=sy;z[n]=sz;r[n]=0;
|
28 | x[++n]=ex;y[n]=ey;z[n]=ez;r[n]=0;
|
29 | for(int i=1;i<=n;i++)
|
30 | {
|
31 | for(int j=i+1;j<=n;j++)
|
32 | {
|
33 | ma[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
|
34 | ma[i][j]=ma[j][i]=sqrt(ma[i][j]*ma[i][j]+(z[i]-z[j])*(z[i]-z[j]))-r[i]-r[j];
|
35 | if(ma[i][j]<0)
|
36 | {
|
37 | ma[i][j]=ma[j][i]=0;
|
38 | }
|
39 | }
|
40 | }
|
41 | for(int k=1;k<=n;k++)
|
42 | {
|
43 | for(int i=1;i<=n;i++)
|
44 | {
|
45 | for(int j=1;j<=n;j++)
|
46 | {
|
47 | if(i!=j&&j!=k&&i!=k)
|
48 | {
|
49 | ma[i][j]=minn(ma[i][j],ma[i][k]+ma[k][j]);
|
50 | }
|
51 | }
|
52 | }
|
53 | }
|
54 | printf("%.0lf\n",ma[n-1][n]*10.00);
|
55 | cin>>n;
|
56 | }
|
57 | return 0;
|
58 | }
|
