A27919. 城市间紧急救援作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。输入输入第一行给出 4 个正整数 n、m、s、d，其中 n（2 ≤ n ≤ 500）是城市的…
填空题
困难
知识点
题目描述
城市间紧急救援
作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。
输入
输入第一行给出 4 个正整数 n、m、s、d，其中 n（2 ≤ n ≤ 500）是城市的个数，顺便假设城市的编号为 0 ~ (n-1)；m 是快速道路的条数；s 是出发地的城市编号；d是目的地的城市编号。 第二行给出 n个正整数，其中第 i 个数是第 i 个城市的救援队的数目，数字间以空格分隔。随后的 m 行中，每行给出一条快速道路的信息，分别是：城市 1、城市 2、快速道路的长度，中间用空格分开，数字均为整数且不超过 500。输入保证救援可行且最优解唯一。
输出
第一行输出最短路径的条数和能够召集的最多的救援队数量。第二行输出从 s 到 d 的路径中经过的城市编号。数字间以空格分隔。
样例输入
4 5 0 3
20 30 40 10
0 1 1
1 3 2
0 3 3
0 2 2
2 3 2样例输出
2 60
0 1 3参考答案
#include <bits/stdc++.h>
using namespace std;
const int N = 505; // 定义最大节点数
const int INF = 1000000; // 定义无穷大
int n, m, s, d; // 定义变量n（节点数），m（边数），s（起点），d（终点）
int saveteam[N], st[N]; // 定义数组saveteam用于存储每个节点的救援队人数，st用于存储到达每个节点的最多救援队人数
int mm[N][N]; // 定义邻接矩阵mm，用于存储图的权重
int vis[N] = {0}; // 定义数组vis，用于标记节点是否已经被访问过
int dis[N]; // 定义数组dis，用于存储从起点到每个节点的最短距离
int father[N]; // 定义数组father，用于存储路径树，即每个节点的父节点
int num[N] = {0}; // 定义数组num，用于存储到达每个节点的路径数量
void Dijkstra() {
fill(dis, dis + N, INF); // 初始化所有节点的距离为无穷大
dis[s] = 0; // 起点到自身的距离为0
num[s] = 1; // 起点的路径数量为1
for (int i = 0; i < n; i++) {
int node = -1, minn = INF; // 定义变量node用于存储当前最近的节点，minn用于存储最小距离
for (int j = 0; j < n; j++) {
if (vis[j] == 0 && minn > dis[j]) {
node = j; // 更新最近的节点
minn = dis[j]; // 更新最小距离
}
}
vis[node] = 1; // 标记当前节点为已访问
if (node == -1) return; // 如果没有找到未访问的节点，则退出
for (int j = 0; j < n; j++) {
if (vis[j] == 0) { // 遍历未访问的节点
if (mm[node][j] != -1 && dis[node] + mm[node][j] < dis[j]) {
father[j] = node; // 更新父节点
dis[j] = dis[node] + mm[node][j]; // 更新距离
st[j] = st[node] + saveteam[j]; // 更新到达该节点的最多救援队人数
num[j] = num[node]; // 更新路径数量
} else if (mm[node][j] != -1 && dis[node] + mm[node][j] == dis[j]) {
if (st[j] < st[node] + saveteam[j]) {
father[j] = node; // 更新父节点
st[j] = st[node] + saveteam[j]; // 更新到达该节点的最多救援队人数
}
num[j] += num[node]; // 更新路径数量
}
}
}
}
}
int main() {
vector<int> sc; // 定义一个向量，用于存储路径
cin >> n >> m >> s >> d; // 读取节点数、边数、起点和终点
for (int i = 0; i < n; i++) {
cin >> saveteam[i];
father[i] = i; // 初始化每个节点的父节点为自己
st[i] = saveteam[i]; // 初始化到达每个节点的救援队人数
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
mm[i][j] = -1; // 初始化邻接矩阵
}
}
for (int i = 0; i < m; i++) {
int a, b, l;
cin >> a >> b >> l;
mm[a][b] = l; // 更新邻接矩阵
mm[b][a] = l; // 无向图，所以需要更新两个方向的权重
}
Dijkstra(); // 调用Dijkstra算法
cout << num[d] << " " << st[d] << "\n"; // 输出到达终点的路径数量和最多救援队人数
int p = d; // 定义变量p，用于存储当前节点
while (1) {
if (p == father[p]) {
sc.push_back(p); // 将当前节点加入路径
break; // 如果当前节点是起点，则退出循环
}
sc.push_back(p); // 将当前节点加入路径
p = father[p]; // 向上追溯父节点
}
for (int i = sc.size() - 1; i > 0; i--) { // 逆序输出路径
cout << sc[i] << " ";
}
cout << sc[0] << "\n";
return 0;
}
上一题
下一题