SP4555 ANARC08F - Einbahnstrasse

在一些城市中，设置单行道（德语称为 Einbahnstrasse）是为了让交通在拥挤地区更加顺畅。这种设计在城市中心尤其是古城如开罗和大马士革等地方非常有用。通过精心规划，驾驶员可以从任何地点到达目的地。然而，这要求司机在规划自己的行程时要小心，避免因为单行道而导致行程过长。有经验的司机知道，任何两点之间可以有多条路径，而且可能有多条道路连接同一对位置。因此，掌握任意两个地点之间的最短路径是必须的！尤其是当驾驶难以操控的车辆（如垃圾车或拖车）时，这一点尤为重要。 你刚刚开始在一家拖车公司工作。公司的拖车停放在企业的车库里。当接到城市中不同地方的电话时，你需要为故障车辆安排拖车。拖运车辆必须按照接单的顺序进行，从故障地点拖回车库。你的工作是为拖车司机提供建议，以最短的路线从各个地点拖运故障车回到车库。每天结束时，你需要向管理层汇报拖车行驶的总距离。

程序会测试一个或多个测试用例。每个测试用例的第一行包含三个数字 $N$、$C$ 和 $R$，由空格分隔。$N$ 表示城市中不同位置的数量，包括公司的车库；$C$ 表示故障车辆数；$R$ 表示城市中的道路数。注意 $0 < N < 100$， $0 \leq C < 1000$， $R < 10000$。第二行包含 $C + 1$ 个单词：第一个是公司车库的位置，其余的是各个故障车的位置。每个位置名不超过 10 个字母，并区分大小写。在接下来的 R 行中，每行描述一条路。道路描述的格式有三种： - A --v-> B - A

对于每个测试用例，打印出拖车所行驶的总距离，用如下格式表示： k. V 其中 k 是测试用例的序号（从 1 开始），V 是结果。 **本翻译由 AI 自动生成**