Description 给出n个星球的名称和三维坐标，距离定义为欧氏距离，其中有m对星球之间存在虫洞，那么这对星球之间距离为0，q次查询，每次查询一对星球之间的最短距离 Input 第一行一整数T表示用例组数，每组用例首先输入一整数n表示星球数量，之后输入每个星球的名字和三维坐标x,y,x，然后是一整数m表示虫洞数量，之后m行每行输入两个星球的名字表示这对星球之间存在虫洞，然后是一整数q表示查询数，之后q行每行两个星球的名字表示查询这两个星球的最短距离(1<=T<=10,1<=n<=60,0<=x,y,z<=2e6,0<=m<=40,1<=q<=20,名字不超过50个字符) Output 对于每次查询，输出这两个星球之间最短距离 Sample Input 3 4 Earth 0 0 0 Proxima 5 0 0 Barnards 5 5 0 Sirius 0 5 0 2 Earth Barnards Barnards Sirius 6 Earth Proxima Earth Barnards Earth Sirius Proxima Earth Barnards Earth Sirius Earth 3 z1 0 0 0 z2 10 10 10 z3 10 0 0 1 z1 z2 3 z2 z1 z1 z2 z1 z3 2 Mars 12345 98765 87654 Jupiter 45678 65432 11111 0 1 Mars Jupiter Sample Output Case 1: The distance from Earth to Proxima is 5 parsecs. The distance from Earth to Barnards is 0 parsecs. The distance from Earth to Sirius is 0 parsecs. The distance from Proxima to Earth is 5 parsecs. The distance from Barnards to Earth is 5 parsecs. The distance from Sirius to Earth is 5 parsecs. Case 2: The distance from z2 to z1 is 17 parsecs. The distance from z1 to z2 is 0 parsecs. The distance from z1 to z3 is 10 parsecs. Case 3: The distance from Mars to Jupiter is 89894 parsecs. Solution 才60个点，建好图Floyd跑一遍即可 Code
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<queue> #include<map> #include<set> #include<ctime> using namespace std; typedef long long ll; #define INF 0x3f3f3f3f #define maxn 66 map<string,int>M; int T,n,m,q,x[maxn],y[maxn],z[maxn]; double dis[maxn][maxn]; string s[maxn]; double get(int i,int j) { return sqrt(pow(x[i]-x[j],2)+pow(y[i]-y[j],2)+pow(z[i]-z[j],2)); } int main() { scanf("%d",&T); for(int Case=1;Case<=T;Case++) { M.clear(); scanf("%d",&n); for(int i=1;i<=n;i++) { cin>>s[i]>>x[i]>>y[i]>>z[i]; M[s[i]]=i; } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dis[i][j]=get(i,j); scanf("%d",&m); while(m--) { string a,b; cin>>a>>b; dis[M[a]][M[b]]=0; } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); scanf("%d",&q); printf("Case %d:\n",Case); while(q--) { string a,b; char c[maxn],d[maxn]; scanf("%s%s",c,d); a=c,b=d; printf("The distance from %s to %s is %.0f parsecs.\n",c,d,dis[M[a]][M[b]]); } } return 0; }