P1603. Risk 题解

这道题是经典的图论最短路径问题，解题的关键在于将地图抽象为图结构，并使用Dijkstra算法计算两点之间的最短路径。

题目分析

题目描述了一个游戏地图，包含20个国家，每个国家与其他国家通过边界相连。要求计算从起始国家到目标国家所需的最少征服次数，即经过的最少国家数量。注意，每次征服只能移动到相邻国家，且路径中的每个国家（包括起点和终点）都被计算在内。

解题思路

1. 图的表示：使用邻接矩阵表示国家之间的连接关系。如果国家i和国家j相邻，则Cost[i][j] = 1。
2. 最短路径算法：由于所有边的权重都是1（每次征服一个国家），可以使用Dijkstra算法计算最短路径。
3. 输入处理：按题目要求处理输入，每个测试用例包含19行国家连接信息和若干查询。
4. 输出格式：按指定格式输出每个查询的结果。

代码实现

以下是完整的C++实现：

#include<iostream>
#include<cstdio>
#include<cstring>
#define MAXNODE 25
#define MAXCOST 9999
using namespace std;

// 输入国家连接信息，构建邻接矩阵
void InputCost(int Cost[][MAXNODE]) {
    int n, k;
    for(int i = 2; i <= 19; i++) {
        scanf("%d", &n);
        for(int j = 0; j < n; j++) {
            scanf("%d", &k);
            Cost[i][k] = 1;
            Cost[k][i] = 1;
        }
    }
}

// Dijkstra算法计算从f到所有其他节点的最短路径
void Dijkstra(int Cost[][MAXNODE], int f, int Distance[], int e) {
    int s[MAXNODE];  // 标记节点是否已找到最短路径
    int mindis, dis;
    int i, j, u;
    
    // 初始化距离数组和标记数组
    for(i = 1; i <= 20; i++) {
        Distance[i] = Cost[f][i];
        s[i] = 0;
    }
    
    s[f] = 1;  // 标记起点
    
    // Dijkstra主循环
    for(i = 1; i <= 20; i++) {
        mindis = MAXCOST;
        u = -1;
        
        // 找到未标记节点中距离最小的节点
        for(j = 1; j <= 20; j++) {
            if(s[j] == 0 && Distance[j] < mindis) {
                u = j;
                mindis = Distance[j];
            }
        }
        
        if(u == -1) break;  // 所有可达节点都已标记
        
        s[u] = 1;  // 标记该节点
        
        // 更新所有未标记节点的距离
        for(j = 1; j <= 20; j++) {
            if(s[j] == 0) {
                dis = Distance[u] + Cost[u][j];
                if(dis < Distance[j]) {
                    Distance[j] = dis;
                }
            }
        }
    }
    
    // 输出结果，注意路径长度需要加1（包含起点）
    printf("%d to %d: %d\n", f, e, Distance[e] + 1);
}

int main() {
    int Cost[MAXNODE][MAXNODE];
    int cnt;
    int kkk = 0;  // 测试用例编号
    int n, k;
    int i, f, e, Distance[MAXNODE];
    
    while(cin >> n) {  // 读取第一个国家的连接信息
        memset(Cost, 0x3f, sizeof(Cost));  // 初始化为无穷大
        
        // 处理第一个国家的连接信息
        while(n--) {
            cin >> k;
            Cost[1][k] = 1;
            Cost[k][1] = 1;
        }
        
        // 处理剩余18个国家的连接信息
        InputCost(Cost);
        
        // 读取查询数量
        cin >> cnt;
        ++kkk;
        printf("Test Set #%d\n", kkk);
        
        // 处理每个查询
        while(cnt--) {
            cin >> f >> e;
            Dijkstra(Cost, f, Distance, e);
        }
        
        putchar(10);  // 每个测试用例后输出空行
    }
    
    return 0;
}

代码解释

1. 邻接矩阵构建：

   • InputCost函数读取19行国家连接信息，构建邻接矩阵。每个连接在矩阵中表示为双向边（Cost[i][j] = Cost[j][i] = 1）。

2. Dijkstra算法：

   • 初始化距离数组Distance，记录从起点到各节点的最短距离。
   • 使用标记数组s记录已找到最短路径的节点。
   • 每次从未标记节点中选择距离最小的节点，更新其邻居的距离。
   • 最终Distance[e]即为从起点到终点的最短路径长度（边数）。

3. 输入输出处理：

   • 主函数读取输入，处理多个测试用例。
   • 每个测试用例包含地图信息和若干查询，按格式输出结果。

注意事项

1. 路径长度计算：题目要求的是经过的国家数量，而Dijkstra算法计算的是边数，因此最终结果需要加1。

2. 初始化：邻接矩阵初始化为无穷大（0x3f3f3f3f），表示节点之间不可达。

3. 双向边：国家之间的连接是双向的，因此在构建邻接矩阵时需要同时设置Cost[i][j]和Cost[j][i]。

通过这种方法，可以高效地计算从任意起点到终点的最短路径，满足题目的要求。