class064 Dijkstra算法、分层图最短路【算法】

class064 Dijkstra算法、分层图最短路【算法】

算法讲解064【必备】Dijkstra算法、分层图最短路
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

code1 743. 网络延迟时间

// Dijkstra算法模版(Leetcode)
// 网络延迟时间
// 有 n 个网络节点,标记为 1 到 n
// 给你一个列表 times,表示信号经过 有向 边的传递时间
// times[i] = (ui, vi, wi),表示从ui到vi传递信号的时间是wi
// 现在,从某个节点 s 发出一个信号
// 需要多久才能使所有节点都收到信号
// 如果不能使所有节点收到信号,返回 -1
// 测试链接 : https://leetcode.cn/problems/network-delay-time

code1 P4779 【模板】单源最短路径(标准版)

// Dijkstra算法模版(洛谷)
// 静态空间实现 : 链式前向星 + 反向索引堆
// 测试链接 : https://www.luogu.com.cn/problem/P4779
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下所有代码,把主类名改成Main,可以直接通过

package class064;

// Dijkstra算法模版(洛谷)
// 静态空间实现 : 链式前向星 + 反向索引堆
// 测试链接 : https://www.luogu.com.cn/problem/P4779
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下所有代码,把主类名改成Main,可以直接通过

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;

public class Code01_DijkstraLuogu {

	public static int MAXN = 100001;

	public static int MAXM = 200001;

	// 链式前向星
	public static int[] head = new int[MAXN];

	public static int[] next = new int[MAXM];

	public static int[] to = new int[MAXM];

	public static int[] weight = new int[MAXM];

	public static int cnt;

	// 反向索引堆
	public static int[] heap = new int[MAXN];

	// where[v] = -1,表示v这个节点,从来没有进入过堆
	// where[v] = -2,表示v这个节点,已经弹出过了
	// where[v] = i(>=0),表示v这个节点,在堆上的i位置
	public static int[] where = new int[MAXN];

	public static int heapSize;

	public static int[] distance = new int[MAXN];

	public static int n, m, s;

	public static void build() {
		cnt = 1;
		heapSize = 0;
		Arrays.fill(head, 1, n + 1, 0);
		Arrays.fill(where, 1, n + 1, -1);
		Arrays.fill(distance, 1, n + 1, Integer.MAX_VALUE);
	}

	// 链式前向星建图
	public static void addEdge(int u, int v, int w) {
		next[cnt] = head[u];
		to[cnt] = v;
		weight[cnt] = w;
		head[u] = cnt++;
	}

	public static void addOrUpdateOrIgnore(int v, int w) {
		if (where[v] == -1) {
			heap[heapSize] = v;
			where[v] = heapSize++;
			distance[v] = w;
			heapInsert(where[v]);
		} else if (where[v] >= 0) {
			distance[v] = Math.min(distance[v], w);
			heapInsert(where[v]);
		}
	}

	public static void heapInsert(int i) {
		while (distance[heap[i]] < distance[heap[(i - 1) / 2]]) {
			swap(i, (i - 1) / 2);
			i = (i - 1) / 2;
		}
	}

	public static int pop() {
		int ans = heap[0];
		swap(0, --heapSize);
		heapify(0);
		where[ans] = -2;
		return ans;
	}

	public static void heapify(int i) {
		int l = 1;
		while (l < heapSize) {
			int best = l + 1 < heapSize && distance[heap[l + 1]] < distance[heap[l]] ? l + 1 : l;
			best = distance[heap[best]] < distance[heap[i]] ? best : i;
			if (best == i) {
				break;
			}
			swap(best, i);
			i = best;
			l = i * 2 + 1;
		}
	}

	public static boolean isEmpty() {
		return heapSize == 0;
	}

	public static void swap(int i, int j) {
		int tmp = heap[i];
		heap[i] = heap[j];
		heap[j] = tmp;
		where[heap[i]] = i;
		where[heap[j]] = j;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StreamTokenizer in = new StreamTokenizer(br);
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		while (in.nextToken() != StreamTokenizer.TT_EOF) {
			n = (int) in.nval;
			in.nextToken(); m = (int) in.nval;
			in.nextToken(); s = (int) in.nval;
			build();
			for (int i = 0, u, v, w; i < m; i++) {
				in.nextToken(); u = (int) in.nval;
				in.nextToken(); v = (int) in.nval;
				in.nextToken(); w = (int) in.nval;
				addEdge(u, v, w);
			}
			dijkstra();
			out.print(distance[1]);
			for (int i = 2; i <= n; i++) {
				out.print(" " + distance[i]);
			}
			out.println();
		}
		out.flush();
		out.close();
		br.close();
	}

	public static void dijkstra() {
		addOrUpdateOrIgnore(s, 0);
		while (!isEmpty()) {
			int v = pop();
			for (int ei = head[v]; ei > 0; ei = next[ei]) {
				addOrUpdateOrIgnore(to[ei], distance[v] + weight[ei]);
			}
		}
	}

}

code2 1631. 最小体力消耗路径

// 最小体力消耗路径
// 你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights
// 其中 heights[row][col] 表示格子 (row, col) 的高度
// 一开始你在最左上角的格子 (0, 0) ,且你希望去最右下角的格子 (rows-1, columns-1)
// (注意下标从 0 开始编号)。你每次可以往 上,下,左,右 四个方向之一移动
// 你想要找到耗费 体力 最小的一条路径
// 一条路径耗费的体力值是路径上,相邻格子之间高度差绝对值的最大值
// 请你返回从左上角走到右下角的最小 体力消耗值
// 测试链接 :https://leetcode.cn/problems/path-with-minimum-effort/

package class064;

import java.util.PriorityQueue;

// 最小体力消耗路径
// 你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights
// 其中 heights[row][col] 表示格子 (row, col) 的高度
// 一开始你在最左上角的格子 (0, 0) ,且你希望去最右下角的格子 (rows-1, columns-1) 
// (注意下标从 0 开始编号)。你每次可以往 上,下,左,右 四个方向之一移动
// 你想要找到耗费 体力 最小的一条路径
// 一条路径耗费的体力值是路径上,相邻格子之间高度差绝对值的最大值
// 请你返回从左上角走到右下角的最小 体力消耗值
// 测试链接 :https://leetcode.cn/problems/path-with-minimum-effort/
public class Code02_PathWithMinimumEffort {

	// 0:上,1:右,2:下,3:左
	public static int[] move = new int[] { -1, 0, 1, 0, -1 };

	public int minimumEffortPath(int[][] heights) {
		// (0,0)源点
		// -> (x,y)
		int n = heights.length;
		int m = heights[0].length;
		int[][] distance = new int[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				distance[i][j] = Integer.MAX_VALUE;
			}
		}
		distance[0][0] = 0;
		boolean[][] visited = new boolean[n][m];
		// 0 : 格子的行
		// 1 : 格子的列
		// 2 : 源点到当前格子的代价
		PriorityQueue<int[]> heap = new PriorityQueue<int[]>((a, b) -> a[2] - b[2]);
		heap.add(new int[] { 0, 0, 0 });
		while (!heap.isEmpty()) {
			int[] record = heap.poll();
			int x = record[0];
			int y = record[1];
			int c = record[2];
			if (visited[x][y]) {
				continue;
			}
			if (x == n - 1 && y == m - 1) {
				// 常见剪枝
				// 发现终点直接返回
				// 不用等都结束
				return c;
			}
			visited[x][y] = true;
			for (int i = 0; i < 4; i++) {
				int nx = x + move[i];
				int ny = y + move[i + 1];
				if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny]) {
					int nc = Math.max(c, Math.abs(heights[x][y] - heights[nx][ny]));
					if (nc < distance[nx][ny]) {
						distance[nx][ny] = nc;
						heap.add(new int[] { nx, ny, nc });
					}
				}
			}
		}
		return -1;
	}

}

code3 778. 水位上升的泳池中游泳

// 水位上升的泳池中游泳
// 在一个 n x n 的整数矩阵 grid 中
// 每一个方格的值 grid[i][j] 表示位置 (i, j) 的平台高度
// 当开始下雨时,在时间为 t 时,水池中的水位为 t
// 你可以从一个平台游向四周相邻的任意一个平台,但是前提是此时水位必须同时淹没这两个平台
// 假定你可以瞬间移动无限距离,也就是默认在方格内部游动是不耗时的
// 当然,在你游泳的时候你必须待在坐标方格里面。
// 你从坐标方格的左上平台 (0,0) 出发
// 返回 你到达坐标方格的右下平台 (n-1, n-1) 所需的最少时间
// 测试链接 : https://leetcode.cn/problems/swim-in-rising-water/

package class064;

import java.util.PriorityQueue;

// 水位上升的泳池中游泳
// 在一个 n x n 的整数矩阵 grid 中
// 每一个方格的值 grid[i][j] 表示位置 (i, j) 的平台高度
// 当开始下雨时,在时间为 t 时,水池中的水位为 t
// 你可以从一个平台游向四周相邻的任意一个平台,但是前提是此时水位必须同时淹没这两个平台
// 假定你可以瞬间移动无限距离,也就是默认在方格内部游动是不耗时的
// 当然,在你游泳的时候你必须待在坐标方格里面。
// 你从坐标方格的左上平台 (0,0) 出发
// 返回 你到达坐标方格的右下平台 (n-1, n-1) 所需的最少时间
// 测试链接 : https://leetcode.cn/problems/swim-in-rising-water/
public class Code03_SwimInRisingWater {

	// 0:上,1:右,2:下,3:左
	public static int[] move = new int[] { -1, 0, 1, 0, -1 };

	public static int swimInWater(int[][] grid) {
		int n = grid.length;
		int m = grid[0].length;
		int[][] distance = new int[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				distance[i][j] = Integer.MAX_VALUE;
			}
		}
		distance[0][0] = grid[0][0];
		boolean[][] visited = new boolean[n][m];
		// 0 : 格子的行
		// 1 : 格子的列
		// 2 : 源点到当前格子的代价
		PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[2] - b[2]);
		heap.add(new int[] { 0, 0, grid[0][0] });
		while (!heap.isEmpty()) {
			int x = heap.peek()[0];
			int y = heap.peek()[1];
			int c = heap.peek()[2];
			heap.poll();
			if (visited[x][y]) {
				continue;
			}
			visited[x][y] = true;
			if (x == n - 1 && y == m - 1) {
				// 常见剪枝
				// 发现终点直接返回
				// 不用等都结束
				return c;
			}
			for (int i = 0, nx, ny, nc; i < 4; i++) {
				nx = x + move[i];
				ny = y + move[i + 1];
				if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny]) {
					nc = Math.max(c, grid[nx][ny]);
					if (nc < distance[nx][ny]) {
						distance[nx][ny] = nc;
						heap.add(new int[] { nx, ny, nc });
					}
				}
			}
		}
		return -1;
	}

}

code4 864. 获取所有钥匙的最短路径

// 获取所有钥匙的最短路径
// 给定一个二维网格 grid ,其中:
// ‘.’ 代表一个空房间、‘#’ 代表一堵、‘@’ 是起点
// 小写字母代表钥匙、大写字母代表锁
// 从起点开始出发,一次移动是指向四个基本方向之一行走一个单位空间
// 不能在网格外面行走,也无法穿过一堵墙
// 如果途经一个钥匙,我们就把它捡起来。除非我们手里有对应的钥匙,否则无法通过锁。
// 假设 k 为 钥匙/锁 的个数,且满足 1 <= k <= 6,
// 字母表中的前 k 个字母在网格中都有自己对应的一个小写和一个大写字母
// 换言之,每个锁有唯一对应的钥匙,每个钥匙也有唯一对应的锁
// 另外,代表钥匙和锁的字母互为大小写并按字母顺序排列
// 返回获取所有钥匙所需要的移动的最少次数。如果无法获取所有钥匙,返回 -1 。
// 测试链接:https://leetcode.cn/problems/shortest-path-to-get-all-keys

package class064;

// 获取所有钥匙的最短路径
// 给定一个二维网格 grid ,其中:
// '.' 代表一个空房间、'#' 代表一堵、'@' 是起点
// 小写字母代表钥匙、大写字母代表锁
// 从起点开始出发,一次移动是指向四个基本方向之一行走一个单位空间
// 不能在网格外面行走,也无法穿过一堵墙
// 如果途经一个钥匙,我们就把它捡起来。除非我们手里有对应的钥匙,否则无法通过锁。
// 假设 k 为 钥匙/锁 的个数,且满足 1 <= k <= 6,
// 字母表中的前 k 个字母在网格中都有自己对应的一个小写和一个大写字母
// 换言之,每个锁有唯一对应的钥匙,每个钥匙也有唯一对应的锁
// 另外,代表钥匙和锁的字母互为大小写并按字母顺序排列
// 返回获取所有钥匙所需要的移动的最少次数。如果无法获取所有钥匙,返回 -1 。
// 测试链接:https://leetcode.cn/problems/shortest-path-to-get-all-keys
public class Code04_ShortestPathToGetAllKeys {

	public static int MAXN = 31;

	public static int MAXM = 31;

	public static int MAXK = 6;

	// 0:上,1:右,2:下,3:左
	public static int[] move = new int[] { -1, 0, 1, 0, -1 };

	public static char[][] grid = new char[MAXN][];

	public static boolean[][][] visited = new boolean[MAXN][MAXM][1 << MAXK];

	// 0 : 行
	// 1 : 列
	// 2 : 收集钥匙的状态
	public static int[][] queue = new int[MAXN * MAXM * (1 << MAXK)][3];

	public static int l, r, n, m, key;

	public static void build(String[] g) {
		l = r = key = 0;
		n = g.length;
		m = g[0].length();
		for (int i = 0; i < n; i++) {
			grid[i] = g[i].toCharArray();
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (grid[i][j] == '@') {
					queue[r][0] = i;
					queue[r][1] = j;
					// 0 : 000000
					queue[r++][2] = 0;
				}
				if (grid[i][j] >= 'a' && grid[i][j] <= 'f') {
					key |= 1 << (grid[i][j] - 'a');
				}
			}
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				for (int s = 0; s <= key; s++) {
					visited[i][j][s] = false;
				}
			}
		}
	}

	public static int shortestPathAllKeys(String[] g) {
		build(g);
		int level = 1;
		while (l < r) {
			for (int k = 0, size = r - l, x, y, s; k < size; k++) {
				x = queue[l][0];
				y = queue[l][1];
				s = queue[l++][2];
				for (int i = 0, nx, ny, ns; i < 4; i++) {
					nx = x + move[i];
					ny = y + move[i + 1];
					ns = s;
					if (nx < 0 || nx == n || ny < 0 || ny == m || grid[nx][ny] == '#') {
						// 越界或者障碍
						continue;
					}
					if (grid[nx][ny] >= 'A' && grid[nx][ny] <= 'F' && ((ns & (1 << (grid[nx][ny] - 'A'))) == 0)) {
						// 是锁,又没有对应的钥匙
						continue;
					}
					if (grid[nx][ny] >= 'a' && grid[nx][ny] <= 'f') {
						// 是某一把钥匙
						ns |= (1 << (grid[nx][ny] - 'a'));
					}
					if (ns == key) {
						// 常见剪枝
						// 发现终点直接返回
						// 不用等都结束
						return level;
					}
					if (!visited[nx][ny][ns]) {
						visited[nx][ny][ns] = true;
						queue[r][0] = nx;
						queue[r][1] = ny;
						queue[r++][2] = ns;
					}
				}
			}
			level++;
		}
		return -1;
	}

}

code5 LCP 35. 电动车游城市

// 电动车游城市
// 小明的电动车电量充满时可行驶距离为 cnt,每行驶 1 单位距离消耗 1 单位电量,且花费 1 单位时间
// 小明想选择电动车作为代步工具。地图上共有 N 个景点,景点编号为 0 ~ N-1
// 他将地图信息以 [城市 A 编号,城市 B 编号,两城市间距离] 格式整理在在二维数组 paths,
// 表示城市 A、B 间存在双向通路。
// 初始状态,电动车电量为 0。每个城市都设有充电桩,
// charge[i] 表示第 i 个城市每充 1 单位电量需要花费的单位时间。
// 请返回小明最少需要花费多少单位时间从起点城市 start 抵达终点城市 end
// 测试链接 : https://leetcode.cn/problems/DFPeFJ/

package class064;

import java.util.ArrayList;
import java.util.PriorityQueue;

// 电动车游城市
// 小明的电动车电量充满时可行驶距离为 cnt,每行驶 1 单位距离消耗 1 单位电量,且花费 1 单位时间
// 小明想选择电动车作为代步工具。地图上共有 N 个景点,景点编号为 0 ~ N-1
// 他将地图信息以 [城市 A 编号,城市 B 编号,两城市间距离] 格式整理在在二维数组 paths,
// 表示城市 A、B 间存在双向通路。
// 初始状态,电动车电量为 0。每个城市都设有充电桩,
// charge[i] 表示第 i 个城市每充 1 单位电量需要花费的单位时间。
// 请返回小明最少需要花费多少单位时间从起点城市 start 抵达终点城市 end
// 测试链接 : https://leetcode.cn/problems/DFPeFJ/
public class Code05_VisitCityMinCost {

	// 电动车总电量,cnt
	public static int electricCarPlan(int[][] paths, int cnt, int start, int end, int[] charge) {
		int n = charge.length;
		ArrayList<ArrayList<int[]>> graph = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			graph.add(new ArrayList<>());
		}
		for (int[] path : paths) {
			graph.get(path[0]).add(new int[] { path[1], path[2] });
			graph.get(path[1]).add(new int[] { path[0], path[2] });
		}
		// n : 0 ~ n-1,不代表图上的点
		// (点,到达这个点的电量)图上的点!
		int[][] distance = new int[n][cnt + 1];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <= cnt; j++) {
				distance[i][j] = Integer.MAX_VALUE;
			}
		}
		distance[start][0] = 0;
		boolean[][] visited = new boolean[n][cnt + 1];
		// 0 : 当前点
		// 1 : 来到当前点的电量
		// 2 : 花费时间
		PriorityQueue<int[]> heap = new PriorityQueue<int[]>((a, b) -> (a[2] - b[2]));
		heap.add(new int[] { start, 0, 0 });
		while (!heap.isEmpty()) {
			int[] record = heap.poll();
			int cur = record[0];
			int power = record[1];
			int cost = record[2];
			if (visited[cur][power]) {
				continue;
			}
			if (cur == end) {
				// 常见剪枝
				// 发现终点直接返回
				// 不用等都结束
				return cost;
			}
			visited[cur][power] = true;
			if (power < cnt) {
				// 充一格电
				// cur, power+1
				if (!visited[cur][power + 1] && cost + charge[cur] < distance[cur][power + 1]) {
					distance[cur][power + 1] = cost + charge[cur];
					heap.add(new int[] { cur, power + 1, cost + charge[cur] });
				}
			}
			for (int[] edge : graph.get(cur)) {
				// 不充电去别的城市
				int nextCity = edge[0];
				int restPower = power - edge[1];
				int nextCost = cost + edge[1];
				if (restPower >= 0 && !visited[nextCity][restPower] && nextCost < distance[nextCity][restPower]) {
					distance[nextCity][restPower] = nextCost;
					heap.add(new int[] { nextCity, restPower, nextCost });
				}
			}
		}
		return -1;
	}

}

code6 P4568 [JLOI2011] 飞行路线

// 飞行路线(语言提供的堆)
// Alice和Bob现在要乘飞机旅行,他们选择了一家相对便宜的航空公司
// 该航空公司一共在n个城市设有业务,设这些城市分别标记为0 ~ n−1
// 一共有m种航线,每种航线连接两个城市,并且航线有一定的价格
// Alice 和 Bob 现在要从一个城市沿着航线到达另一个城市,途中可以进行转机
// 航空公司对他们这次旅行也推出优惠,他们可以免费在最多k种航线上搭乘飞机
// 那么 Alice 和 Bob 这次出行最少花费多少
// 测试链接 : https://www.luogu.com.cn/problem/P4568
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下所有代码,把主类名改成Main,可以直接通过

code6 P4568 [JLOI2011] 飞行路线

// 飞行路线(自己手撸的堆)
// Alice和Bob现在要乘飞机旅行,他们选择了一家相对便宜的航空公司
// 该航空公司一共在n个城市设有业务,设这些城市分别标记为0 ~ n−1
// 一共有m种航线,每种航线连接两个城市,并且航线有一定的价格
// Alice 和 Bob 现在要从一个城市沿着航线到达另一个城市,途中可以进行转机
// 航空公司对他们这次旅行也推出优惠,他们可以免费在最多k种航线上搭乘飞机
// 那么 Alice 和 Bob 这次出行最少花费多少
// 测试链接 : https://www.luogu.com.cn/problem/P4568
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下所有代码,把主类名改成Main,可以直接通过

package class064;

// 飞行路线(自己手撸的堆)
// Alice和Bob现在要乘飞机旅行,他们选择了一家相对便宜的航空公司
// 该航空公司一共在n个城市设有业务,设这些城市分别标记为0 ~ n−1
// 一共有m种航线,每种航线连接两个城市,并且航线有一定的价格
// Alice 和 Bob 现在要从一个城市沿着航线到达另一个城市,途中可以进行转机
// 航空公司对他们这次旅行也推出优惠,他们可以免费在最多k种航线上搭乘飞机
// 那么 Alice 和 Bob 这次出行最少花费多少
// 测试链接 : https://www.luogu.com.cn/problem/P4568
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下所有代码,把主类名改成Main,可以直接通过

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class Code06_FlightPath2 {

	public static int MAXN = 10001;

	public static int MAXM = 100001;

	public static int MAXK = 11;

	// 链式前向星建图需要
	public static int[] head = new int[MAXN];

	public static int[] next = new int[MAXM];

	public static int[] to = new int[MAXM];

	public static int[] weight = new int[MAXM];

	public static int cnt;

	// Dijkstra需要
	public static int[][] distance = new int[MAXN][MAXK];

	public static boolean[][] visited = new boolean[MAXN][MAXK];

	// 自己写的普通堆,静态结构,推荐
	// 注意是自己写的普通堆,不是反向索引堆
	// 因为(点编号,使用免费路线的次数),两个参数的组合才是图中的点
	// 两个参数的组合对应一个点(一个堆的下标),所以反向索引堆不好写
	// 其实也能实现,二维点变成一维下标即可
	// 但是会造成很多困惑,索性算了,就手写普通堆吧
	public static int[][] heap = new int[MAXM * MAXK][3];

	public static int heapSize;

	public static int n, m, k, s, t;

	public static void build() {
		cnt = 1;
		heapSize = 0;
		for (int i = 0; i < n; i++) {
			head[i] = 0;
			for (int j = 0; j <= k; j++) {
				distance[i][j] = Integer.MAX_VALUE;
				visited[i][j] = false;
			}
		}
	}

	public static void addEdge(int u, int v, int w) {
		next[cnt] = head[u];
		to[cnt] = v;
		weight[cnt] = w;
		head[u] = cnt++;
	}

	public static void push(int u, int t, int c) {
		heap[heapSize][0] = u;
		heap[heapSize][1] = t;
		heap[heapSize][2] = c;
		int i = heapSize++;
		while (heap[i][2] < heap[(i - 1) / 2][2]) {
			swap(i, (i - 1) / 2);
			i = (i - 1) / 2;
		}
	}

	public static int u, use, cost;

	public static void pop() {
		u = heap[0][0];
		use = heap[0][1];
		cost = heap[0][2];
		swap(0, --heapSize);
		heapify();
	}

	public static void heapify() {
		int i = 0;
		int l = 1;
		while (l < heapSize) {
			int best = l + 1 < heapSize && heap[l + 1][2] < heap[l][2] ? l + 1 : l;
			best = heap[best][2] < heap[i][2] ? best : i;
			if (best == i) {
				break;
			}
			swap(best, i);
			i = best;
			l = i * 2 + 1;
		}
	}

	public static void swap(int i, int j) {
		int[] tmp = heap[i];
		heap[i] = heap[j];
		heap[j] = tmp;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StreamTokenizer in = new StreamTokenizer(br);
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		while (in.nextToken() != StreamTokenizer.TT_EOF) {
			n = (int) in.nval;
			in.nextToken(); m = (int) in.nval;
			in.nextToken(); k = (int) in.nval;
			in.nextToken(); s = (int) in.nval;
			in.nextToken(); t = (int) in.nval;
			build();
			for (int i = 0, a, b, c; i < m; i++) {
				in.nextToken(); a = (int) in.nval;
				in.nextToken(); b = (int) in.nval;
				in.nextToken(); c = (int) in.nval;
				addEdge(a, b, c);
				addEdge(b, a, c);
			}
			out.println(dijkstra());
		}
		out.flush();
		out.close();
		br.close();
	}

	public static int dijkstra() {
		distance[s][0] = 0;
		push(s, 0, 0);
		while (heapSize > 0) {
			pop();
			if (visited[u][use]) {
				continue;
			}
			visited[u][use] = true;
			if (u == t) {
				// 常见剪枝
				// 发现终点直接返回
				// 不用等都结束
				return cost;
			}
			for (int ei = head[u], v, w; ei > 0; ei = next[ei]) {
				v = to[ei];
				w = weight[ei];
				if (use < k && distance[v][use + 1] > distance[u][use]) {
					// 使用免费
					distance[v][use + 1] = distance[u][use];
					push(v, use + 1, distance[v][use + 1]);
				}
				if (distance[v][use] > distance[u][use] + w) {
					// 不用免费
					distance[v][use] = distance[u][use] + w;
					push(v, use, distance[v][use]);
				}
			}
		}
		return -1;
	}

}

2023-12-9 19:21:42

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/233450.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

机器学习基本概念介绍 2023

笔记来源于&#xff1a; https://www.youtube.com/watch?vphQK8xZpgoU&t172s https://www.youtube.com/watch?vXLyPFnephpY&t645s Machine/Deep Learning 机器学习概况来说&#xff0c;让机器具备自动找函式的能力 &#xff08;Machine Learning 约等于 Looking …

MongoDB的条件操作符

本文主要介绍MongoDB的条件操作符。 目录 MongoDB条件操作符1.比较操作符2.逻辑操作符3.元素操作符4.数组操作符5.文本搜索操作符 MongoDB条件操作符 MongoDB的条件操作符主要分为比较操作符、逻辑操作符、元素操作符、数组操作符、文本搜索操作符等几种类型。 以下是这些操作…

unity Mesh Simplify 1.10(模型优化工具:查看面数,降低面数灯)

提示&#xff1a;文章有错误的地方&#xff0c;还望诸位大神不吝指教&#xff01; 文章目录 前言一、面板参数详解说明二、使用方法总结 前言 有时候想对模型优化一下&#xff0c;奈何又不会建模方面的。虽然我感觉它的数值不大对&#xff0c;但是不影响我们优化顶点数嘛。 Me…

python 画条形图(柱状图)

目录 前言 基础介绍 月度开支的条形图 前言 条形图&#xff08;bar chart&#xff09;&#xff0c;也称为柱状图&#xff0c;是一种以长方形的长度为变量的统计图表&#xff0c;长方形的长度与它所对应的变量数值呈一定比例。 当使用 Python 画条形图时&#xff0c;通常会使…

0基础学java-day14-(集合)

一、集合 前面我们保存多个数据使用的是数组&#xff0c;那么数组有不足的地方&#xff0c;我们分析一下 1.数组 2 集合 数据类型也可以不一样 3.集合的框架体系 Java 的集合类很多&#xff0c;主要分为两大类&#xff0c;如图 &#xff1a;[背下来] package com.hspedu.c…

如何确认网站是否有漏洞,如何找出网站存在的漏洞,找到漏洞该如何处理

如何确认网站或者服务器是否有漏洞 判断一个网站是否是存在漏洞的方法&#xff1a; 1.可以借助德迅云安全漏洞扫描功能来检查漏洞。 2.打开德迅云安全首页&#xff0c;点击最上面导航栏中的“安全产品”。 3.滑到“漏洞扫描”&#xff0c;选择“产品价格”服务。 4.选择您需…

CleanMyMac2024破解版激活码许可证密钥

CleanMyMac X是一款颇受欢迎的专业清理软件&#xff0c;拥有十多项强大的功能&#xff0c;可以进行系统清理、清空废纸篓、清除大旧型文件、程序卸载、除恶意软件、系统维护等等&#xff0c;并且这款清理软件操作简易&#xff0c;非常好上手&#xff0c;特别适用于那些刚入手苹…

51单片机的内核架构组成 介绍

对于51单片机相信很多电子信息或者相关专业的朋友应该都不会感觉陌生&#xff0c;很多专业在大学课程中开设的单片机课程就是使用的51单片机进行授课和学习的。51单片机的内容相较于其他高性能复杂的单片机来说&#xff0c;架构相对简单一些&#xff0c;寄存器也少很多&#xf…

vite脚手架,配置动态生成路由,添加不同的layout以及meta配置

实现效果&#xff0c;配置了layout和对应的路由的meta 我想每个模块添加对应的layout&#xff0c;下边演示一层layout及对应的路由 约束规则&#xff1a; 每个模块下&#xff0c;添加对应的 layout.vue 文件 每个文件夹下的 index.vue 是要渲染的页面路由 每个渲染的页面路由对…

Kafka-快速实战

Kafka介绍 ChatGPT对于Apache Kafka的介绍&#xff1a; Apache Kafka是一个分布式流处理平台&#xff0c;最初由LinkedIn开发并于2011年开源。它主要用于解决大规模数据的实时流式处理和数据管道问题。 Kafka是一个分布式的发布-订阅消息系统&#xff0c;可以快速地处理高吞吐…

案例课4——智齿客服

1.公司介绍 智齿科技&#xff0c;一体化客户联络中心解决方案提供商。提供基于「客户联络中心」场景的一体化解决方案&#xff0c;包括公域私域、营销服务、软件BPO的三维一体化。 智齿科技不断整合前沿的人工智能及大数据技术&#xff0c;已构建形成呼叫中心、机器人「在线语音…

46. 全排列

全排列 描述 : 给定一个不含重复数字的数组 nums &#xff0c;返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 题目 : LeetCode 46.全排列 : 46. 全排列 分析 : 这里给个非常好的视频 : LeetCode力扣 46. 全排列Permutations_哔哩哔哩_bilibili 解析: class S…

双水平呼吸机算法怎么写?(其实是记录自己写呼吸的心得)

双水平正压呼吸机是什么&#xff1f; 市面上的双水平呼吸机&#xff0c;就是包含有双水平模式的呼吸机&#xff0c;其中一般也会包含单水平模式。其中正压的意思&#xff0c;就是抬高呼吸的压力基线&#xff0c;使吸气顺畅一些。 呼吸机硬件参考 不能给太详细&#xff0c;就给…

机械中常用的一些术语

目录 一、OEMSOP:SOP编写指南 WI(标准作业指导书):标准作业程序 &#xff08;SOP&#xff09;:SOP和WI的区别&#xff1a;一、PFC、FMEA、PCP、WIPPAP、PSW&#xff1a; 一、OEM 1.OEM&#xff1a; 原始设备制造商OEM&#xff08;Original Equipment Manufacturer&#xff09;…

从零开始的C++(二十一)

C11 1.列表初始化&#xff1a; //允许以下代码正确运行int a[]{1,2,3};//效果与int a[]{1,2,3}一致 即允许省略等于号。同时&#xff0c;允许用花括号对所有自定义类型和内置类型进行初始化&#xff0c;而非以前花括号只能对数组进行初始化。利用花括号对自定义类型初始化时…

数据结构和算法-单链表

数据结构和算法-单链表 1. 链表介绍 链表是有序的列表&#xff0c;但是它在内存中是存储如下 图1 单链表示意图 小结: 链表是以节点的方式存储每个节点包含data域&#xff0c;next域&#xff0c;指向下一个节点。如图&#xff1a;发现链表的各个节点不一定是连续存储。比如地…

C语言函数详解

# 函数的概念 对于函数&#xff0c;我想大家应该并不陌生&#xff0c;在数学中就存在函数的概念&#xff0c;比如&#xff1a;一次函数 ykxb &#xff0c;k和b都是常数&#xff0c;给⼀个任意的x&#xff0c;就能得到⼀个y值。 在C语言中也有函数的概念&#xff0c;函数也被称为…

unity 模型生成PNG图片并导出(可以任意控制方向和大小,本文提供三种方案)

提示&#xff1a;文章有错误的地方&#xff0c;还望诸位大神不吝指教&#xff01; 文章目录 前言一、插件RuntimePreviewGenerator&#xff08;方案一&#xff09;二、unity 官方提供的接口&#xff08;方案二&#xff09;三、方法三&#xff0c;可以处理单个模型&#xff0c;也…

STM32基于USB串口通信应用开发

✅作者简介&#xff1a;热爱科研的嵌入式开发者&#xff0c;修心和技术同步精进&#xff0c; 代码获取、问题探讨及文章转载可私信。 ☁ 愿你的生命中有够多的云翳,来造就一个美丽的黄昏。 &#x1f34e;获取更多嵌入式资料可点击链接进群领取&#xff0c;谢谢支持&#xff01;…

git自动更新功能

确认权限 因为一般Linux系统网页用的www 或 www-data用户和用户组,所以要实现自动来去,首先要在www用户权限下生成ssh密钥,不然没有权限,其次就是,要把用root用户拉去的代码,批量改成www用户 1. 给www权限 vi /etc/sudoers www ALL=(ALL) NOPASSWD:/bin/chow…