SHPATH - The Shortest Path

题意翻译

题目描述: 给定一些城市。每一条直接连接两个城市的交通线都有一个大于零的交通费用。需要找出若干对城市间的最小交通费用。 每条城市间交通路径的费用和最多为200000。每个城市的名称是一个包含小写字母a~z的字符串,长度最多为10。 输入格式: 第一行输入一个数s,测试数据的组数。(s<=10) 对于每一组测试数据,第一行输入一个数n,城市的数量。(n<=10000) 之后对于每个n,输入一个字符串p,即城市的名称。 下一行输入一个数p,与这个城市直接相邻的城市的数量。 之后p行,每行输入两个数nr和cost。nr为与该城市相邻的城市的编号(编号按输入顺序从1开始),cost为这条路径的交通费用。 接下来输入一个数r,查询组数。(r<=100) 之后r行,每行输入两个字符串,起点和终点城市的名称。 每两组测试数据之间用空行隔开。 输出格式: 对于每一个查询,输出一行,两个城市间最小的交通费用。

题目描述

You are given a list of cities. Each direct connection between two cities has its transportation cost (an integer bigger than 0). The goal is to find the paths of minimum cost between pairs of cities. Assume that the cost of each path (which is the sum of costs of all direct connections belongning to this path) is at most 200000. The name of a city is a string containing characters a,...,z and is at most 10 characters long.

输入输出格式

输入格式


``` s [the number of tests <= 10] n [the number of cities <= 10000] NAME [city name] p [the number of neighbours of city NAME] nr cost [nr - index of a city connected to NAME (the index of the first city is 1)] [cost - the transportation cost] r [the number of paths to find <= 100] NAME1 NAME2 [NAME1 - source, NAME2 - destination] [empty line separating the tests] ```

输出格式


``` cost [the minimum transportation cost from city NAME1 to city NAME2 (one per line)] ```

输入输出样例

输入样例 #1

1
4
gdansk
2
2 1
3 3
bydgoszcz
3
1 1
3 1
4 4
torun
3
1 3
2 1
4 1
warszawa
2
2 4
3 1
2
gdansk warszawa
bydgoszcz warszawa

输出样例 #1

3
2

说明

**Warning: large Input/Output data, be careful with certain languages**