With our time on Earth coming to an end, Cooper and Amelia have volunteered to undertake
what could be the most important mission in human history: travelling beyond this galaxy
to discover whether mankind has a future among the stars. Fortunately, astronomers have identified
several potentially inhabitable planets and have also discovered that some of these planets
have wormholes joining them, which effectively makes the travel distance between these wormhole
connected planets zero. For all other planets, the travel distance between them is simply the Euclidean
distance between the planets. Given the location of Earth, planets, and wormholes, find
the shortest travel distance between any pairs of planets.
Input
• The first line of input is a single integer, T (1 ≤ T ≤ 10) the number of test cases.
• Each test case consists of planets, wormholes, and a set of distance queries.
• The planets list for a test case starts with a single integer, p (1 ≤ p ≤ 60), the number of
planets. Following this are p lines, where each line contains a planet name along with the
planet’s integer coordinates, i.e. name x y z (0 ≤ x, y, x ≤ 2 · 106
) The names of the planets
will consist only of ASCII letters and numbers, and will always start with an ASCII letter.
Planet names are case-sensitive (Earth and earth are distinct planets). The length of a planet
name will never be greater than 50 characters. All coordinates are given in parsecs.
• The wormholes list for a test case starts with a single integer, w (0 ≤ w ≤ 40), the number
of wormholes, followed by the list of w wormholes. Each wormhole consists of two planet
names separated by a space. The first planet name marks the entrance of wormhole, and the
second planet name marks the exit from the wormhole. The planets that mark wormholes
will be chosen from the list of planets given in the preceding section. Note: you can’t enter
a wormhole at its exit.
• The queries list for a test case starts with a single integer, q (1 ≤ q ≤ 20), the number of
queries. Each query consists of two planet names separated by a space. Both planets will
have been listed in the planet list.
2014 Pacific Northwest Region Programming Contest—Division 2 27
Output
For each test case, output a line, “Case i:”, the number of the ith test case. Then, for each
query in that test case, output a line that states “The distance from planet1
to planet2
is d
parsecs.”, where the planets are the names from the query and d is the shortest possible travel
distance between the two planets. Round d to the nearest integer.
Sample Input Sample Output
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
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.
题意：给定行星的位置坐标，再给出虫洞的出口以及入口，最后给出若干询问，问两个星球的距离；
注意题目中的数据，p<=60，那么我们用Floyd 即可解决，当然对于虫洞 ，自然设为0即可，处理过后，询问就是O(1)即可完成；
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<string>
#include<bitset>
#include<ctime>
#include<deque>
typedef long long ll;
using namespace std;
typedef unsigned long long int ull;
#define maxn 300005
#define ms(x) memset(x,0,sizeof(x))
#define Inf 0x7fffffff
#define inf 0x3f3f3f3f
const long long int mod = 1e9 + 7;
#define pi acos(-1.0)
#define pii pair<int,int>
#define eps 1e-7
#define pll pair<ll,ll>
ll quickpow(ll a, ll b) {
ll ans = 1;
a = a % mod;
while (b > 0) {
if (b % 2)ans = ans * a;
b = b / 2;
a = a * a;
}
return ans;
}
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a%b);
}
int x[maxn], y[maxn], z[maxn];
string s[maxn];
int n;
map<string, int>mp;
double dis[5000][5000];
double dist(int i, int j) {
return sqrt(1.0*(x[i] - x[j])*(x[i] - x[j]) + 1.0*(y[i] - y[j])*(y[i] - y[j])+1.0*(z[i]-z[j])*(z[i]-z[j]));
}
int main()
{
ios::sync_with_stdio(false);
int T;
cin >> T;
int cnt = 0;
while (T--) {
cin >> n;
int i, j;
cnt++;
mp.clear();
for (i = 1; i <= n; i++) {
cin >> s[i] >> x[i] >> y[i] >> z[i];
mp[s[i]] = i;
}
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
dis[i][j] = dist(i, j);
}
}
int m;
cin >> m;
while (m--) {
string t, r;
cin >> t >> r;
dis[mp[t]][mp[r]] = 0;
}
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
dis[j][k] = min(dis[j][k], dis[j][i] + dis[i][k]);
}
}
}
int q;
cin >> q;
printf("Case %d:\n", cnt);
while (q--) {
string r, t;
char tmp1[maxn], tmp2[maxn];
cin >> tmp1 >> tmp2;
r = tmp1; t = tmp2;
printf("The distance from %s to %s is %.0f parsecs.\n", tmp1, tmp2, dis[mp[r]][mp[t]]);
}
}
}