Problem 1037: Wormhole
Time Limits: 5000 MS Memory Limits: 200000 KB
64-bit interger IO format: %lld Java class name: Main
Description
With our time on Earth coming to an end, Cooper and Amelia have volunteered to under- take 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 iden- tified 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 Eu- clidean 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.
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
Output for Sample Input
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.
Hint
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
懒人用map写邻接表，果然够麻烦的，神奇的是写完可以直接编译，居然没报错，懂套路就是一SPFA水题。只是点从int换成了string。
代码：
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<string>
#include<deque>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define INF 0x3f3f3f3f
#define MM(x) memset(x,0,sizeof(x))
using namespace std;
typedef long long LL;
map<string,vector<pair<string,double> > >E;
map<string,double>d;
map<string,double>::iterator mit;
struct info
{
string s;
double x,y,z;
};
double dx(const info &a,const info &b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z));
}
void spfa(const string &s,const string &t)
{
d[s]=0;
priority_queue<pair<double,string> >Q;
vector<pair<string,double> >::iterator it;
Q.push(pair<double,string>(-d[s],s));
while (!Q.empty())
{
string now=Q.top().second;
Q.pop();
for (it=E[now].begin(); it!=E[now].end(); it++)
{
string v=it->first;
if(d[v]>d[now]+it->second)
{
d[v]=d[now]+it->second;
Q.push(pair<double,string>(-d[v],v));
}
}
}
return ;
}
int main(void)
{
int tcase,i,j;
info pla[70];
cin>>tcase;
map<string,vector<pair<string,double> > >::iterator it;
for (int ca=1; ca<=tcase; ca++)
{
E.clear();
d.clear();
int p,q;
string s;
double x,y,z;
cin>>p;
for (i=0; i<p; i++)
{
cin>>pla[i].s>>pla[i].x>>pla[i].y>>pla[i].z;
}
for (i=0; i<p; i++)
{
d[pla[i].s]=1e9;
for (j=i+1; j<p; j++)
{
E[pla[i].s].push_back(pair<string,double>(pla[j].s,dx(pla[i],pla[j])));
E[pla[j].s].push_back(pair<string,double>(pla[i].s,dx(pla[i],pla[j])));
d[pla[j].s]=1e9;
}
}
string t;
int w;
vector<pair<string,double> >::iterator it;
cin>>w;
while (w--)
{
cin>>s>>t;
for (it=E[s].begin(); it!=E[s].end(); it++)
{
if(it->first==t)
it->second=0;
}
}
cin>>q;
cout<<"Case "<<ca<<":"<<endl;
while (q--)
{
cin>>s>>t;
for (mit=d.begin(); mit!=d.end(); mit++)
mit->second=1e9;
spfa(s,t);
printf("The distance from %s to %s is %.0lf parsecs.
",s.c_str(),t.c_str(),d[t]);
}
}
return 0;
}