题目描述

Slow Boat to China航运公司需要开发一个程序来快速为客户提供运输报价。运输成本取决于货物大小和所需运输航段数量。每个航段连接两个仓库，但由于并非所有仓库之间都有直达航段，货物可能需要通过多个航段才能从起始仓库运抵目标仓库。

数据规格

• 每个数据集包含$1$到$30$个仓库，每个仓库用两个大写字母作为代码
• 航段是双向的，可存在于任意两个不同仓库之间
• 运输成本计算公式：货物大小 × 所需航段数 × 100美元

输入格式

第一行包含$1$到$10$之间的整数，表示数据集数量。每个数据集包含：

1. 三个整数$M,N,P$：
   • $M$：仓库数量（$1 \leq M \leq 30$）
   • $N$：航段数量（$0 \leq N \leq \frac{M(M-1)}{2}$）
   • $P$：运输请求数量（$0 \leq P \leq 10$）
2. $M$个仓库代码（空格分隔）
3. $N$行航段信息，格式为"XX YY"
4. $P$行运输请求，每行格式为：货物大小 AA BB（AA=起始仓库，BB=目标仓库）

输出格式

第一行输出应为 SHIPPING ROUTES OUTPUT 。对于每个数据集，应有一个输出部分，列出该输出部分对应的是哪个数据集，随后是 P 行所需信息。这 P 行中的每一行应列出相应运输的最低成本，或者短语 NO SHIPMENT POSSIBLE（无法运输 ）。输出的结尾也应加以说明。生成与以下示例一致的输出。

每个运输请求输出最低成本（格式：\$数字）或"NO SHIPMENT POSSIBLE"

样例输入

2
6 7 5
AA CC QR FF DD AB
AA CC
CC QR
DD CC
AA DD
AA AB
DD QR
AB DD
5 AA AB
14 DD CC
1 CC DD
2 AA FF
13 AB QR
3 0 1
AA BB CC
5 AA CC

样例输出

SHIPPING ROUTES OUTPUT
DATA SET 1
$500
$1400
$100
NO SHIPMENT POSSIBLE
$2600
DATA SET 2
NO SHIPMENT POSSIBLE
END OF OUTPUT

来源

Mid-Atlantic 1996

关键点说明

• 需要计算任意两仓库间的最短路径（最少航段数）
• 当不可达时输出"NO SHIPMENT POSSIBLE"
• 成本计算示例：5单位货物从AA到AB（1个航段）→ \$5×1×100=\$500