SP780 ARCHPLG - The Archipelago

比特兰是一个由矩形岛屿组成的群岛国家。这个群岛共有 $1 \le n \le 1000$ 个岛屿。每个岛形状都是矩形，这让比特兰的制图师感到很满意。 比特兰的岛屿面积较小，且土地不够肥沃，所以每一块（自然也是矩形的）耕地都受到特别的保护。简单来说，人们被禁止进入这些区域，以防发生意外。除此之外，其他区域对居民完全开放，可以随意出入。 不同岛屿之间可以通过渡轮进行交通往来。每个岛屿上有 $0 \le b \le 10$ 个码头，码头之间可以跨岛相连。已知的渡轮连接总数为 $0 \le m \le 100000$。至于岛屿上的其他基础设施，几乎没有其他信息。具体来说，岛屿上的交通方式仅限步行。 接下来，我们要解决的问题是：约翰，一位比特兰的销售经理，常常被要求从一个地方出差到另一个地方。他对此颇为不悦，更希望像其他比特兰人一样，在海滩俱乐部里玩一款名为普托的战略游戏。请你帮助他找到一种省时的出行方案。 ### 任务 规划出约翰在岛屿上步行和乘渡轮的最快路线之一。假设约翰步行时，以每单位比特兰时间（BH）行进一单位比特兰距离（BM）。你还可以假设渡轮的出发时间几乎与约翰到达码头的时间同步，只需将步行时间尽量接近整数即可。

第一行输入测试用例的数量 $t$。对于每个测试用例： - 输入一行，表示岛屿的数量 $n$。 - 接下来，每个岛屿的描述如下： ``` 名称 w h [岛屿的宽和高] b [码头的数量] [每个码头的信息格式如下：] 名称 x y [码头的名称及其坐标] F [受限区域的数量 F] ``` 所有坐标均为根据岛屿左上角测量的非负整数，单位为 BM。 假设所有受限区域互不重叠。所有岛屿的描述结束后，会给出所有渡轮连接信息（连接是双向的）。 ``` m [总连接数] [每个连接的信息格式] NB1 NW1 NB2 NW2 时间 [起始码头名称及所在岛屿、目标码头及所需时间] ... [后续连接信息] ... NBS NWS NBC NWC [约翰的出发点和目的地码头] ```

输出约翰从岛屿 NWS 的码头 NBS 到岛屿 NWC 的码头 NBC 最短路径的描述，格式如下： ``` case nr Y [测试用例编号] T [总旅行时间，单位为 BH] NBS NWS ... [经过的码头] ... NBC NWC [空行] [继续下一个测试用例] ``` 如果两个连续码头位于同一岛屿上，并且需要步行，则中间点也必须列出，如示例所示。 **本翻译由 AI 自动生成**