[bbone=cpp,73]
include
include
include
include
include
using namespace std;
struct mycomparison
{
bool operator() (const pair& lhs, const pair& rhs) const
{
return (lhs.first>rhs.first);
}
};
int N;
bool visited[100001];
vector > edges[100001];
map cities;
priority_queue, vector >, mycomparison > Q;
int main()
{
int T,M,R,a,b,i;
int loc, dist, nextloc, nextdist;
char city[20];
pair S;
scanf("%d", &T);
while(T--)
{
scanf("%d", &N);
cities.clear();
for(i = 1; i <= N; i++)
{
edges[i].clear();
scanf("%s", city);
cities[std::string(city)] = i;
scanf("%d", &M);
while(M--)
{
scanf("%d %d", &a, &b);
edges[i].push_back(make_pair(a,b));
}
}
scanf("%d", &R);
while(R--)
{
for(i = 1; i <= N; i++)
visited[i] = false;
scanf("%s", city);
a = cities[std::string(city)];
scanf("%s", city);
b = cities[std::string(city)];
// Add the initial state for the starting point
Q.push(make_pair(0,a));
while(!Q.empty())
{
S = Q.top();
Q.pop();
loc = S.second;
dist = S.first;
// Check to see that we haven't already found a shorter path to this node
if(visited[loc])
continue;
// This is the shortest path to this node, ignore all other possibilities for this node
visited[loc] = true;
// If this distance is greater than T, then no other time can come in under T, we're done
if(loc == b)
{
printf("%d\n", dist);
while(!Q.empty())
Q.pop();
break;
}
// If we haven't reached the end, push all the endpoints from this location onto the queue
// if they haven't already been visited
for(i = 0; i < edges[loc].size(); i++)
{
nextloc = edges[loc][i].first;
nextdist = edges[loc][i].second + dist;
if(!visited[nextloc])
Q.push(make_pair(nextdist,nextloc));
}
}
if(!visited[b])
printf("-1\n");
}
}
return 0;
}
[/bbone]