P1603. 风险游戏

题目描述

《风险》是一款棋盘游戏，玩家通过征服国家来扩张势力。游戏中，同一国家的军队只能攻击与其接壤的国家，征服后军队可进入新国家。玩家常需要通过一系列征服行动，将大量军队从起始国家调遣至目标国家，此时需选择中间国家，使得最少征服的国家数量（包括目标国家）。

给定一个由20个国家组成的地图，每个国家与1-19个其他国家接壤。你的任务是：对于每组起始国家和目标国家，计算从起始到目标至少需要征服的国家数量（包括目标国家，若起始与目标相同则为0）。

输入格式

输入包含多组测试用例，每组格式如下：

1. 地图描述（第1-19行）：
   • 第I行（1 ≤ I < 20）包含整数X，后跟X个大于I的整数J，表示国家I与国家J接壤（仅列出I < J的情况，避免重复）。
2. 查询描述（第20行及之后）：
   • 第20行是整数N（1 ≤ N ≤ 100），表示查询数量。
   • 接下来N行，每行两个整数A和B（1 ≤ A,B ≤ 20，A ≠ B），表示起始国家和目标国家。

输入以文件结束符（EOF）终止，保证任意两国之间至少存在一条路径。

输出格式

对于每组测试用例，输出：

1. 首行：Test Set #T，其中T为测试用例编号（从1开始）。
2. 接下来N行，每行格式为：A to B : K，其中K为从A到B最少需要征服的国家数量。
3. 每组输出后换行。

输入示例 1

1 3  
2 3 4  
3 4 5 6  
1 6  
1 7  
2 12 13  
1 8  
2 9 10  
1 11  
1 11  
2 12 17  
1 14  
2 14 15  
2 15 16  
1 16  
1 19  
2 18 19  
1 20  
1 20  
5  
1 20  
2 9  
19 5  
18 19  
16 20  

输出示例 1

Test Set #1  
1 to 20: 7  
2 to 9: 5  
19 to 5: 6  
18 to 19: 2  
16 to 20: 2  

来源

South Central USA 1997