1003：
使用迪杰特斯拉算法，同时需要更新最大救援团队（如果发现了路径相同的路径，还需要更新最大救援团队）
详细解析：x迪杰斯特拉算法——求最短路径-CSDN博客
#include <bits/stdc++.h>
using namespace std;const int N = 510; // 最大城市数量
const int INF = 0x3f3f3f3f; // 无穷大，表示不可达的距离int n, m, c1, c2; // 城市数量，道路数量，起点城市，终点城市
int g[N][N], dist[N], rescue[N], num_paths[N], max_rescue[N];
bool st[N]; // 标记每个城市是否已确定最短路径// 迪杰斯特拉算法实现
void dijkstra() {// 初始化memset(dist, 0x3f, sizeof dist); // 最短距离初始化为无穷大memset(num_paths, 0, sizeof num_paths); // 最短路径数量初始化为0memset(max_rescue, 0, sizeof max_rescue); // 最大救援团队数初始化为0dist[c1] = 0; // 起点到起点的距离为0num_paths[c1] = 1; // 起点到起点的路径数量为1max_rescue[c1] = rescue[c1]; // 起点的最大救援团队数为自身的救援团队数for (int i = 0; i < n; i++) {int t = -1; // t代表当前未确定最短路径的城市for (int j = 0; j < n; j++) {if (!st[j] && (t == -1 || dist[t] > dist[j])) {t = j; // 找到距离最小且未确定的城市}}if (t == -1) break; // 如果没有可选的城市，退出循环st[t] = true; // 标记城市t的最短路径已确定// 更新城市t的所有邻接城市的距离for (int j = 0; j < n; j++) {if (g[t][j] != INF) { // 如果t和j之间有道路// 发现更短路径if (dist[j] > dist[t] + g[t][j]) {dist[j] = dist[t] + g[t][j]; // 更新最短距离num_paths[j] = num_paths[t]; // 更新路径数量max_rescue[j] = max_rescue[t] + rescue[j]; // 更新最大救援团队数} // 如果发现相同长度的路径else if (dist[j] == dist[t] + g[t][j]) {num_paths[j] += num_paths[t]; // 增加该路径的数量max_rescue[j] = max(max_rescue[j], max_rescue[t] + rescue[j]); // 更新最大救援团队数}}}}
}int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n >> m >> c1 >> c2; // 输入城市数量，道路数量，起点和终点memset(g, 0x3f, sizeof g); // 初始化图的邻接矩阵为无穷大，表示没有直接连接的道路// 输入每个城市的救援团队数量for (int i = 0; i < n; i++) {cin >> rescue[i];}// 输入每条道路的信息while (m--) {int a, b, l;cin >> a >> b >> l;g[a][b] = g[b][a] = l; // 设置无向图中两城市间的距离}dijkstra(); // 调用迪杰斯特拉算法// 输出从c1到c2的最短路径数量和最大救援团队数cout << num_paths[c2] << " " << max_rescue[c2] << '\n';return 0;
}
1004：
1. 树的表示与构建：
- 树的表示：题目给定了一个树的结构，每个节点有唯一的
id（数字表示），且每个非叶子节点有若干个子节点。我们可以使用一个二维数组或vector来存储这棵树，其中node[i]存储的是节点i的所有子节点。 - 树的构建：从输入中读取每个非叶子节点及其子节点，将这些子节点存入相应的数组或
vector中。
2. 深度优先搜索（DFS）：
- DFS 的概念：DFS 是一种遍历树或图的算法，从一个节点开始，沿着一个分支走到底（访问完所有可能的子节点），然后回溯到上一层节点，继续沿另一个分支深入，直到访问完所有节点为止。
- 在本题中的应用：从根节点（编号为 1 的节点）开始，使用 DFS 遍历整棵树。每次进入一个节点时，如果这个节点没有子节点，就表明它是一个叶子节点，应该在当前的深度层计数（
cnt[depth]++）。
3. 记录叶子节点数：
- 层次记录：DFS 的过程中，当前节点所在的深度是递归传递的参数。对于每一个深度
depth，我们记录该深度层的叶子节点数量。 - 更新最大深度：每当发现一个新的叶子节点时，我们会更新树的最大深度
maxDeep，以便最终确定输出结果的范围。
#include <bits/stdc++.h>
using namespace std;// 全局变量
int n, m; // n 是节点总数，m 是非叶子节点数
vector<int> node[105]; // 每个节点的孩子节点列表，最多支持 105 个节点
int cnt[105]; // 每一层的叶子节点计数数组
int maxDeep = -1; // 记录树的最大深度，用于最终输出// 深度优先搜索函数，u 是当前节点编号，deep 是当前节点的深度
void dfs(int u, int deep) {// 如果当前节点没有孩子节点，则它是一个叶子节点if(node[u].empty()){cnt[deep]++; // 当前深度的叶子节点计数加一maxDeep = max(maxDeep, deep); // 更新最大深度return ;}// 遍历当前节点的所有孩子节点for(int i = 0; i < node[u].size(); i++) {dfs(node[u][i], deep + 1); // 对每个孩子节点递归调用 dfs，并且深度加一}
}int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // 快速输入输出cin >> n >> m; // 读取节点总数 n 和非叶子节点数 mfor(int i = 0; i < m; i++){int id, k; // id 是当前非叶子节点编号，k 是其孩子节点的数量cin >> id >> k;for(int j = 0; j < k; j++){int child; cin >> child; // 读取每个孩子节点的编号node[id].push_back(child); // 将该孩子节点添加到当前节点的孩子列表中}}dfs(1, 0); // 从根节点（编号 1）开始，深度为 0 进行深度优先搜索// 输出每一层的叶子节点数for(int i = 0; i <= maxDeep; i++){cout << cnt[i]; // 输出当前层的叶子节点数if(i != maxDeep) cout << " "; // 如果不是最后一层，输出空格}return 0;
}