怎么做网站的网盘,书店网站模板,小规模公司需要交哪些税,中国建设银行网站官网class064 Dijkstra算法、分层图最短路【算法】
算法讲解064【必备】Dijkstra算法、分层图最短路
code1 743. 网络延迟时间
// Dijkstra算法模版#xff08;Leetcode#xff09; // 网络延迟时间 // 有 n 个网络节点#xff0c;标记为 1 到 n // 给你一个列表 timesLeetcode // 网络延迟时间 // 有 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 : 源点到当前格子的代价PriorityQueueint[] heap new PriorityQueueint[]((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 // 你可以从一个平台游向四周相邻的任意一个平台但是前提是此时水位必须同时淹没这两个平台 // 假定你可以瞬间移动无限距离也就是默认在方格内部游动是不耗时的 // 当然在你游泳的时候你必须待在坐标方格里面。 // 你从坐标方格的左上平台 (00) 出发 // 返回 你到达坐标方格的右下平台 (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
// 你可以从一个平台游向四周相邻的任意一个平台但是前提是此时水位必须同时淹没这两个平台
// 假定你可以瞬间移动无限距离也就是默认在方格内部游动是不耗时的
// 当然在你游泳的时候你必须待在坐标方格里面。
// 你从坐标方格的左上平台 (00) 出发
// 返回 你到达坐标方格的右下平台 (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 : 源点到当前格子的代价PriorityQueueint[] 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 : 000000queue[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 {// 电动车总电量cntpublic static int electricCarPlan(int[][] paths, int cnt, int start, int end, int[] charge) {int n charge.length;ArrayListArrayListint[] 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 : 花费时间PriorityQueueint[] heap new PriorityQueueint[]((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, power1if (!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
