L2-001 紧急救援

这是一道典型的最短路径问题。

#include <stdio.h>
#include <stdbool.h>
#include <limits.h>

#define MAXN 500  // 最大城市数量

int N, M, S, D;  // 城市数量、道路数量、起点、终点
int rescue[MAXN];  // 每个城市的救援队数量
int dist[MAXN];  // 从起点到每个城市的最短距离
int num[MAXN];  // 从起点到每个城市的最短路径数量
int teams[MAXN];  // 从起点到每个城市能够召集的最多救援队数量
int pre[MAXN];  // 记录路径的前驱节点
bool visited[MAXN];  // 记录节点是否被访问过
int graph[MAXN][MAXN];  // 邻接矩阵表示图

// Dijkstra 算法实现
void dijkstra(int start) {
    // 初始化
    for (int i = 0; i < N; i++) {
        dist[i] = INT_MAX;  // 初始化距离为无穷大
        num[i] = 0;  // 初始化最短路径数量为 0
        teams[i] = 0;  // 初始化救援队数量为 0
        visited[i] = false;  // 初始化所有节点为未访问
        pre[i] = -1;  // 初始化前驱节点为 -1
    }
    dist[start] = 0;  // 起点到自身的距离为 0
    num[start] = 1;  // 起点到自身的最短路径数量为 1
    teams[start] = rescue[start];  // 起点能够召集的救援队数量为起点的救援队数量

    // 主循环
    for (int i = 0; i < N; i++) {
        // 找到未访问节点中距离最小的节点
        int u = -1;
        for (int j = 0; j < N; j++) {
            if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
                u = j;  // 更新当前最小距离节点
            }
        }
        if (u == -1) break;  // 所有节点已访问，退出循环
        visited[u] = true;  // 标记当前节点为已访问

        // 更新邻接节点
        for (int v = 0; v < N; v++) {
            if (!visited[v] && graph[u][v] != INT_MAX) {  // 如果节点 v 未访问且 u 到 v 有边
                if (dist[u] + graph[u][v] < dist[v]) {  // 如果通过 u 到 v 的路径更短
                    dist[v] = dist[u] + graph[u][v];  // 更新最短距离
                    num[v] = num[u];  // 更新最短路径数量
                    teams[v] = teams[u] + rescue[v];  // 更新救援队数量
                    pre[v] = u;  // 更新前驱节点
                } else if (dist[u] + graph[u][v] == dist[v]) {  // 如果路径长度相同
                    num[v] += num[u];  // 增加最短路径数量
                    if (teams[u] + rescue[v] > teams[v]) {  // 如果救援队数量更多
                        teams[v] = teams[u] + rescue[v];  // 更新救援队数量
                        pre[v] = u;  // 更新前驱节点
                    }
                }
            }
        }
    }
}

// 输出路径
void printPath(int end) {
    if (end == -1) return;  // 递归终止条件
    printPath(pre[end]);  // 递归输出前驱节点
    printf("%d", end);  // 输出当前节点
    if (end != D) printf(" ");  // 如果不是终点，输出空格
}

int main() {
    // 输入
    scanf("%d %d %d %d", &N, &M, &S, &D);  // 输入城市数量、道路数量、起点、终点
    for (int i = 0; i < N; i++) {
        scanf("%d", &rescue[i]);  // 输入每个城市的救援队数量
    }
    // 初始化图的邻接矩阵
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            graph[i][j] = INT_MAX;  // 初始化所有边为不可达
        }
    }
    // 输入道路信息
    for (int i = 0; i < M; i++) {
        int city1, city2, length;
        scanf("%d %d %d", &city1, &city2, &length);  // 输入道路信息
        graph[city1][city2] = length;  // 更新邻接矩阵
        graph[city2][city1] = length;  // 无向图，双向更新
    }

    // 运行 Dijkstra 算法
    dijkstra(S);

    // 输出结果
    printf("%d %d\n", num[D], teams[D]);  // 输出最短路径数量和最多救援队数量
    printPath(D);  // 输出路径
    printf("\n");  // 换行

    return 0;
}