L2-001 紧急救援(Java)

2024-03-28数据结构与算法4 分钟168 次阅读
AI 摘要鱼粮不足,AI 今天先歇着 · 正文在下面

题目

作为一个城市的应急救援队伍的负责人,你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候,你的任务是带领你的救援队尽快赶往事发地,同时,一路上召集尽可能多的救援队。

输入格式:
输入第一行给出4个正整数N{N}、M{M}、S{S}、D{D},其中N{N}(2≤N≤500){(2\leq N\leq500)}是城市的个数,顺便假设城市的编号为0{0} ~ (N−1){(N-1)};M{M}是快速道路的条数;S{S}是出发地的城市编号;D{D}是目的地的城市编号。

第二行给出N{N}个正整数,其中第i{i}个数是第i{i}个城市的救援队的数目,数字间以空格分隔。随后的M{M}行中,每行给出一条快速道路的信息,分别是:城市1、城市2、快速道路的长度,中间用空格分开,数字均为整数且不超过500。输入保证救援可行且最优解唯一。

输出格式:
第一行输出最短路径的条数和能够召集的最多的救援队数量。第二行输出从S{S}到D{D}的路径中经过的城市编号。数字间以空格分隔,输出结尾不能有多余空格。

输入样例:

sh 复制代码
4 5 0 3
20 30 40 10
0 1 1
1 3 2
0 3 3
0 2 2
2 3 2

输出样例:

sh 复制代码
2 60
0 1 3
sh 复制代码
代码长度限制					16 KB
时间限制						200 ms
内存限制						64 MB

题解

思路:题目求起点s到达终点d的最短路径,故我们可以用迪杰斯特拉算法求最短单源路径,又由于题目还需要在此基础上,判断相同路径的

java 复制代码
import java.util.*;

// L2-001 紧急救援
public class Main {

	static final int MAXN = 500;
	static final int INF = Integer.MAX_VALUE;
	static int[][] graph = new int[MAXN][MAXN];; // 存储 城市a 到 城市b 的距离
	static int[] rescueTeams = new int[MAXN]; // 每个城市的救援队数量
	static int[] dist = new int[MAXN]; // 存储从 起点s 到 每个城市 的最短路径
	static int[] dist_count = new int[MAXN]; // 存储 s 到达 每个城市 的最短路径数量
	static int[] maxRescue = new int[MAXN]; // 存储从 s 到 每个城市 可以召集的最多救援队数量。
	static boolean[] visited = new boolean[MAXN]; // 标记当前城市是否可到达
	static int[] paths = new int[MAXN]; // 前驱节点数组。存储到达每个城市的前一个城市,用于最后回溯找到路径。

	/**
	 * N 城市个数 M 快速道路的条数 S 出发地的城市编号 D 目的地的城市编号
	 */
	static int n, m, s, d;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		// N(2≤N≤500)是城市的个数; M是快速道路的条数;S是出发地的城市编号;D是目的地的城市编号。
		n = sc.nextInt();
		m = sc.nextInt();
		s = sc.nextInt();
		d = sc.nextInt();

		for (int[] row : graph) {
			Arrays.fill(row, INF);
		}

		for (int i = 0; i < n; i++) {
			rescueTeams[i] = sc.nextInt(); // 第i个城市的救援队的数目
		}

		for (int i = 0; i < m; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			int w = sc.nextInt();
			// 记录两节点之间的距离
			graph[a][b] = graph[b][a] = w;
		}

		// 初始化paths数组
		Arrays.fill(paths, -1);

		dijkstra(s);

		System.out.println(dist_count[d] + " " + maxRescue[d]);

		// 输出路径,根据栈的特性(先进后出)
		Stack<Integer> path = new Stack<>();
		for (int v = d; v != -1; v = paths[v]) {
			path.push(v);
		}

		while (!path.isEmpty()) {
			System.out.print(path.pop());
			if (!path.isEmpty()) {
				System.out.print(" ");
			}
		}
	}

//	4 5 0 3
//	20 30 40 10
//	0 1 1
//	1 3 2
//	0 3 3
//	0 2 2
//	2 3 2

	/**
	 * 迪杰斯特拉
	 * 
	 * @param s 起点
	 */
	private static void dijkstra(int s) {
		// 初始化到达每个节点的最短距离为无穷大
		Arrays.fill(dist, INF);
		// 初始化到达每个节点的最短路径数量为0
		Arrays.fill(dist_count, 0);
		// 初始化到达每个节点可以召集的最多救援队数量为0
		Arrays.fill(maxRescue, 0);
		// 初始化所有节点为未访问状态
		Arrays.fill(visited, false);

		// 初始化
		dist[s] = 0; // 起点s到自己的最短距离为0
		dist_count[s] = 1; // 自己到自己的路径只有一条
		// 设置到达自己的最大救援队数量为自己
		maxRescue[s] = rescueTeams[s];

		// 对图中的所有节点进行遍历,每次找出一条最短的边,如果与当前起点相连,且距离最短,就做处理
		for (int i = 0; i < n; i++) {
			int minD = INF; // 记录这个最短路径值
			int u = -1; // 找出未访问过的最短路径的节点编号
			// 寻找未访问的、dist值最小的节点
			for (int j = 0; j < n; j++) {
				if (!visited[j] && dist[j] < minD) {
					minD = dist[j];
					u = j;
				}
			}

			// 如果没有找到这样的节点,说明剩余的所有节点都不可达,跳出循环
			if (u == -1) {
				break;
			}

			// 标记节点u为已访问
			visited[u] = true;

			// 遍历所有节点,更新通过 minId 节点到其他未访问节点的最短路径
			for (int v = 0; v < n; v++) {
				// 邻接节点v还未处理,判断 u 和 v 之间是否连通
				if (!visited[v] && graph[u][v] != INF) {
					// 如果从 u出发达到v,比之前记录的最短路径短,则更新
					if (dist[u] + graph[u][v] < dist[v]) {
						// 更新起点到到达节点v的最短路径
						dist[v] = dist[u] + graph[u][v];
						// 更新起点到到达节点v的最短路径数量
						dist_count[v] = dist_count[u];
						// 更新从🕖到达节点v的最大救援数量
						maxRescue[v] = maxRescue[u] + rescueTeams[v];
						// 更新节点v的上一个节点,用于回溯路径
						paths[v] = u;

						// 如果当前节点u出发到v的距离与之前已经记录的相等
					} else if (dist[u] + graph[u][v] == dist[v]) {
						// 则增加起点到达节点v的最短路径数量,相当于多个路径可以到达v,并且距离相等
						dist_count[v] += dist_count[u];
						// 如果当前路径的救援队数量多于别的路径,则更新
						if (maxRescue[u] + rescueTeams[v] > maxRescue[v]) {
							// 更新最大救援队数量
							maxRescue[v] = maxRescue[u] + rescueTeams[v];
							// 重新更新前驱结点
							paths[v] = u;
						} else if (maxRescue[u] + rescueTeams[v] == maxRescue[v]) {
							// 当存在多条路径且救援队数量相同时,可以选择不更新paths[v],或者根据具体需求处理
						}
					}
				}
			}
		}
	}
}

Java 的时间限制与C++一样。。。最后一个没跑过。
image.png

觉得有用就点个赞,不用登录也能读

评论

0 条
登录 之后才能评论
—
还没有评论,来说第一句