其中leg理解为路（双向）即可。


POJ1529
Shipping Routes 
航路
描述：
The Slow Boat to China Shipping company needs a program to help them quickly quote costs to prospective customers. 
某船需要给客户预期报价。
The cost of a shipment depends on the size of the shipment and on how many shipping legs it requires.
花费依赖于货物量和它需要 的leg数。
A shipping leg connects two warehouses, but since every pair of warehouses is not directly connected by a leg, it might require more than one leg to send a shipment from one warehouse to another. 
一个leg连接两个仓库，但两个仓库之间可能需要的leg数可能要多于1个（间接相连）。
A data set can represent from 1 to 30 warehouses. A two-letter code name will identify each warehouse (capital letters only). 
一个数据集合可以表示1～30个仓库，一个两个大写字母组成的名字标识了每个仓库。
Shipping legs can exist between any two distinct warehouses. 
leg可以在任何两个不同的仓库之间。
All legs are bidirectional. 
所有的leg都是双向的。
The cost of a shipment is equal to the size of the shipment times the number of shipping legs required times $100. 
一个货物的花费等于需要的leg数量乘以$100。
The input to the program identifies the warehouse code names and the existence of all shipping legs. 
输入给出了所有的仓库名字和所有的leg。
For a given shipping request, consisting of the size of the shipment, the source warehouse and the destination warehouse, the program will output the best (cheapest) cost for the shipment, if it is possible to send shipments from the requested source to the requested destination. 
程序输出一个船的最小花费（由货物量的大小组成），若能将货物从起点送到终点。 
Alternately, the program must state that the request cannot be fulfilled.
若要求不能满足（不能从起点送达终点），程序应该说明。

输入：
The first line will contain an integer from 1 to 10 inclusive that represents the number of data sets in the input file. 
第一行给出测试数据的个数（1～10）。
Each data set represents a new shipping configuration. 
每组数据都是独立的。
The first line of data in a data set will contain three integers, say M, N, and P: 
每组数据的第一行包括三个整数M N P
M is an integer from 1 to 30 inclusive representing the number of warehouses in the data set; 
1<=M<=30，表示仓库的数量。
N is an integer from 0 to M*(M-1)/2 inclusive that represents the number of legs between warehouses in the data set; 
0<=N<=M*(M-1)/2，表示leg数。
P is an integer from 0 to 10 inclusive that represents the number of shipping requests for which cost information is required. 
0<=P<=10，表示船请求计算花费的请求数量。
The second line of data in a data set contains M two-letter code names for the M warehouses of the data sets. Only capital letters are used. A single blank separates code names. 
第二行包括M个仓库的名字。只包括大写字母，中间用一个空格分隔。
N lines follow the line of code names, containing shipping leg information in the format: ``XX YY", with XX and YY being the codes for two distinct warehouses in the set that have a direct link (a shipping leg) between them. There will be a single blank between the warehouse codes. 
接下来N行，包括leg的信息。格式为“XX YY”，表示XX和YY仓库（XX！＝YY）有直连的leg。XX和YY中间有一个空格分隔。
The N lines of shipping leg information are followed by P lines of shipping requests, one request per line. Each shipping request will begin with an integer between 1 and 20 inclusive that represents the size of the shipment. The shipment size will be followed by a pair of code names in the format ``AA BB", with AA and BB being the code for two distinct warehouses in the set which represent the source and destination of the requested shipment. 
接下来的P行包括了船的所有请求，每个请求一行。
每个请求的开始给出货物量的大小（>=1, <=20），然后给出“AA BB”，表示请求从AA送到BB。
The input will be valid and consistent. 
输入保证合理性。
A shipping leg will only be represented once within a data set. 
在一组数据中，每个leg只会被描述一次。
Data about legs will always refer to warehouses that have been identified as belonging to the data set. 
leg涉及到的仓库一定是给定的仓库。
See the example below for clarification of the input format.
看示例的输入格式会更加清晰。

输出：
The first line of output should read ``SHIPPING ROUTES OUTPUT". 
第一行输出“SHIPPING ROUTES OUTPUT”。
For each data set there should be a section of output enumerating which data set the output section represents followed by P lines of the required information. 
Each of the P lines should list either the cheapest cost of the respective shipment or the phrase ``NO SHIPMENT POSSIBLE". 
对于P个请求，每个请求应该输出最小花费或“NO SHIPMENT POSSIBLE”。
The end of the output should be noted also. Produce output consistent with the example below.
输出结尾应该输出“END OF OUTPUT”。参见示例输出。

• Re:贴翻译的果断好人啊，比贴代码的有用多了 (0) escalation 2011-07-12 19:41:06