当前位置: 首页 > news >正文

个人网站建设规划表网架钢构公司

个人网站建设规划表,网架钢构公司,南宁seo优化公司,厚街手机网站制作class065 A星、Floyd、Bellman-Ford与SPFA【算法】 2023-12-9 19:27:02 算法讲解065【必备】A星、Floyd、Bellman-Ford与SPFA code1 A*算法模版 // A*算法模版#xff08;对数器验证#xff09; package class065;import java.util.PriorityQueue;// A*算法模版#xff…class065 A星、Floyd、Bellman-Ford与SPFA【算法】 2023-12-9 19:27:02 算法讲解065【必备】A星、Floyd、Bellman-Ford与SPFA code1 A*算法模版 // A*算法模版对数器验证 package class065;import java.util.PriorityQueue;// A*算法模版对数器验证 public class Code01_AStarAlgorithm {// 0:上1:右2:下3:左public static int[] move new int[] { -1, 0, 1, 0, -1 };// Dijkstra算法// grid[i][j] 0 代表障碍// grid[i][j] 1 代表道路// 只能走上、下、左、右不包括斜线方向// 返回从(startX, startY)到(targetX, targetY)的最短距离public static int minDistance1(int[][] grid, int startX, int startY, int targetX, int targetY) {if (grid[startX][startY] 0 || grid[targetX][targetY] 0) {return -1;}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[startX][startY] 1;boolean[][] visited new boolean[n][m];PriorityQueueint[] heap new PriorityQueue((a, b) - a[2] - b[2]);// 0 : 行// 1 : 列// 2 : 从源点出发到达当前点的距离heap.add(new int[] { startX, startY, 1 });while (!heap.isEmpty()) {int[] cur heap.poll();int x cur[0];int y cur[1];if (visited[x][y]) {continue;}visited[x][y] true;if (x targetX y targetY) {return distance[x][y];}for (int i 0, nx, ny; i 4; i) {nx x move[i];ny y move[i 1];if (nx 0 nx n ny 0 ny m grid[nx][ny] 1 !visited[nx][ny] distance[x][y] 1 distance[nx][ny]) {distance[nx][ny] distance[x][y] 1;heap.add(new int[] { nx, ny, distance[x][y] 1 });}}}return -1;}// A*算法// grid[i][j] 0 代表障碍// grid[i][j] 1 代表道路// 只能走上、下、左、右不包括斜线方向// 返回从(startX, startY)到(targetX, targetY)的最短距离public static int minDistance2(int[][] grid, int startX, int startY, int targetX, int targetY) {if (grid[startX][startY] 0 || grid[targetX][targetY] 0) {return -1;}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[startX][startY] 1;boolean[][] visited new boolean[n][m];// 0 : 行// 1 : 列// 2 : 从源点出发到达当前点的距离 当前点到终点的预估距离PriorityQueueint[] heap new PriorityQueue((a, b) - a[2] - b[2]);heap.add(new int[] { startX, startY, 1 f1(startX, startY, targetX, targetY) });while (!heap.isEmpty()) {int[] cur heap.poll();int x cur[0];int y cur[1];if (visited[x][y]) {continue;}visited[x][y] true;if (x targetX y targetY) {return distance[x][y];}for (int i 0, nx, ny; i 4; i) {nx x move[i];ny y move[i 1];if (nx 0 nx n ny 0 ny m grid[nx][ny] 1 !visited[nx][ny] distance[x][y] 1 distance[nx][ny]) {distance[nx][ny] distance[x][y] 1;heap.add(new int[] { nx, ny, distance[x][y] 1 f1(nx, ny, targetX, targetY) });}}}return -1;}// 曼哈顿距离public static int f1(int x, int y, int targetX, int targetY) {return (Math.abs(targetX - x) Math.abs(targetY - y));}// 对角线距离public static int f2(int x, int y, int targetX, int targetY) {return Math.max(Math.abs(targetX - x), Math.abs(targetY - y));}// 欧式距离public static double f3(int x, int y, int targetX, int targetY) {return Math.sqrt(Math.pow(targetX - x, 2) Math.pow(targetY - y, 2));}// 为了测试public static int[][] randomGrid(int n) {int[][] grid new int[n][n];for (int i 0; i n; i) {for (int j 0; j n; j) {if (Math.random() 0.3) {// 每个格子有30%概率是0grid[i][j] 0;} else {// 每个格子有70%概率是1grid[i][j] 1;}}}return grid;}// 为了测试public static void main(String[] args) {int len 100;int testTime 10000;System.out.println(功能测试开始);for (int i 0; i testTime; i) {int n (int) (Math.random() * len) 2;int[][] grid randomGrid(n);int startX (int) (Math.random() * n);int startY (int) (Math.random() * n);int targetX (int) (Math.random() * n);int targetY (int) (Math.random() * n);int ans1 minDistance1(grid, startX, startY, targetX, targetY);int ans2 minDistance2(grid, startX, startY, targetX, targetY);if (ans1 ! ans2) {System.out.println(出错了!);}}System.out.println(功能测试结束);System.out.println(性能测试开始);int[][] grid randomGrid(4000);int startX 0;int startY 0;int targetX 3900;int targetY 3900;long start, end;start System.currentTimeMillis();int ans1 minDistance1(grid, startX, startY, targetX, targetY);end System.currentTimeMillis();System.out.println(运行dijskra算法结果: ans1 , 运行时间(毫秒) : (end - start));start System.currentTimeMillis();int ans2 minDistance2(grid, startX, startY, targetX, targetY);end System.currentTimeMillis();System.out.println(运行A*算法结果: ans2 , 运行时间(毫秒) : (end - start));System.out.println(性能测试结束);}} code2 P2910 [USACO08OPEN] Clear And Present Danger S // Floyd算法模版洛谷 // 测试链接 : https://www.luogu.com.cn/problem/P2910 // 请同学们务必参考如下代码中关于输入、输出的处理 // 这是输入输出处理效率很高的写法 // 提交以下所有代码把主类名改成Main可以直接通过 package class065;// Floyd算法模版洛谷 // 测试链接 : https://www.luogu.com.cn/problem/P2910 // 请同学们务必参考如下代码中关于输入、输出的处理 // 这是输入输出处理效率很高的写法 // 提交以下所有代码把主类名改成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 Code02_Floyd {public static int MAXN 101;public static int MAXM 10001;public static int[] path new int[MAXM];public static int[][] distance new int[MAXN][MAXN];public static int n, m, ans;// 初始时设置任意两点之间的最短距离为无穷大表示任何路不存在public static void build() {for (int i 0; i n; i) {for (int j 0; j n; j) {distance[i][j] Integer.MAX_VALUE;}}}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;for (int i 0; i m; i) {in.nextToken();path[i] (int) in.nval - 1;}// 这道题给的图是邻接矩阵的形式// 任意两点之间的边权都会给定// 所以显得distance初始化不太必要// 但是一般情况下distance初始化一定要做build();for (int i 0; i n; i) {for (int j 0; j n; j) {in.nextToken();distance[i][j] (int) in.nval;}}floyd();ans 0;for (int i 1; i m; i) {ans distance[path[i - 1]][path[i]];}out.println(ans);}out.flush();out.close();br.close();}public static void floyd() {// O(N^3)的过程// 枚举每个跳板// 注意跳板要最先枚举跳板要最先枚举跳板要最先枚举for (int bridge 0; bridge n; bridge) { // 跳板for (int i 0; i n; i) {for (int j 0; j n; j) {// i - .....bridge .... - j// distance[i][j]能不能缩短// distance[i][j] min ( distance[i][j] , distance[i][bridge] distance[bridge][j])if (distance[i][bridge] ! Integer.MAX_VALUE distance[bridge][j] ! Integer.MAX_VALUE distance[i][j] distance[i][bridge] distance[bridge][j]) {distance[i][j] distance[i][bridge] distance[bridge][j];}}}}}} code3 787. K 站中转内最便宜的航班 // Bellman-Ford算法应用不是模版 // k站中转内最便宜的航班 // 有 n 个城市通过一些航班连接。给你一个数组 flights // 其中 flights[i] [fromi, toi, pricei] // 表示该航班都从城市 fromi 开始以价格 pricei 抵达 toi。 // 现在给定所有的城市和航班以及出发城市 src 和目的地 dst你的任务是找到出一条最多经过 k 站中转的路线 // 使得从 src 到 dst 的 价格最便宜 并返回该价格。 如果不存在这样的路线则输出 -1。 // 测试链接 : https://leetcode.cn/problems/cheapest-flights-within-k-stops/ package class065;import java.util.Arrays;// Bellman-Ford算法应用不是模版 // k站中转内最便宜的航班 // 有 n 个城市通过一些航班连接。给你一个数组 flights // 其中 flights[i] [fromi, toi, pricei] // 表示该航班都从城市 fromi 开始以价格 pricei 抵达 toi。 // 现在给定所有的城市和航班以及出发城市 src 和目的地 dst你的任务是找到出一条最多经过 k 站中转的路线 // 使得从 src 到 dst 的 价格最便宜 并返回该价格。 如果不存在这样的路线则输出 -1。 // 测试链接 : https://leetcode.cn/problems/cheapest-flights-within-k-stops/ public class Code03_BellmanFord {// Bellman-Ford算法// 针对此题改写了松弛逻辑课上讲了细节public static int findCheapestPrice(int n, int[][] flights, int start, int target, int k) {int[] cur new int[n];Arrays.fill(cur, Integer.MAX_VALUE);cur[start] 0;for (int i 0; i k; i) {int[] next Arrays.copyOf(cur, n);for (int[] edge : flights) {// a - b , wif (cur[edge[0]] ! Integer.MAX_VALUE) {next[edge[1]] Math.min(next[edge[1]], cur[edge[0]] edge[2]);}}cur next;}return cur[target] Integer.MAX_VALUE ? -1 : cur[target];}} P3385 【模板】负环 // Bellman-Ford SPFA优化模版洛谷 // 给定一个 n个点的有向图请求出图中是否存在从顶点 1 出发能到达的负环 // 负环的定义是一条边权之和为负数的回路。 // 测试链接 : https://www.luogu.com.cn/problem/P3385 // 请同学们务必参考如下代码中关于输入、输出的处理 // 这是输入输出处理效率很高的写法 // 提交以下所有代码把主类名改成Main可以直接通过 package class065;// Bellman-Ford SPFA优化模版洛谷 // 给定一个 n个点的有向图请求出图中是否存在从顶点 1 出发能到达的负环 // 负环的定义是一条边权之和为负数的回路。 // 测试链接 : https://www.luogu.com.cn/problem/P3385 // 请同学们务必参考如下代码中关于输入、输出的处理 // 这是输入输出处理效率很高的写法 // 提交以下所有代码把主类名改成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 Code04_SPFA {public static int MAXN 2001;public static int MAXM 6001;// 链式前向星建图需要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;// SPFA需要public static int MAXQ 4000001;// 源点出发到每个节点的距离表public static int[] distance new int[MAXN];// 节点被松弛的次数public static int[] updateCnt new int[MAXN];// 哪些节点被松弛了放入队列public static int[] queue new int[MAXQ];public static int l, r;// 节点是否已经在队列中public static boolean[] enter new boolean[MAXN];public static void build(int n) {cnt 1;l r 0;Arrays.fill(head, 1, n 1, 0);Arrays.fill(enter, 1, n 1, false);Arrays.fill(distance, 1, n 1, Integer.MAX_VALUE);Arrays.fill(updateCnt, 1, n 1, 0);}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 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));in.nextToken();int cases (int) in.nval;for (int i 0, n, m; i cases; i) {in.nextToken(); n (int) in.nval;in.nextToken(); m (int) in.nval;build(n);for (int j 0, u, v, w; j m; j) {in.nextToken(); u (int) in.nval;in.nextToken(); v (int) in.nval;in.nextToken(); w (int) in.nval;if (w 0) {addEdge(u, v, w);addEdge(v, u, w);} else {addEdge(u, v, w);}}out.println(spfa(n) ? YES : NO);}out.flush();out.close();br.close();}// Bellman-Ford SPFA优化的模版public static boolean spfa(int n) {distance[1] 0;updateCnt[1];queue[r] 1;enter[1] true;while (l r) {int u queue[l];enter[u] false;for (int ei head[u], v, w; ei 0; ei next[ei]) {v to[ei];w weight[ei];if (distance[u] w distance[v]) {distance[v] distance[u] w;if (!enter[v]) {if (updateCnt[v] n) {return true;}queue[r] v;enter[v] true;}}}}return false;}} 2023-12-9 21:16:55
http://mrfarshtey.net/news/84018/

相关文章:

  • 网站制作做网站特种工建设网站
  • wordpress数据过滤宁波seo服务推广软件
  • 做微信公众号的网站吗管理咨询公司起名大气上口的
  • html5 手机网站 图标淮南发布
  • 怎么建设一个购买卡密的网站境外网站网站有哪些
  • 网站建设软文手机免费做网站怎么做网站
  • 河北软件开发网站建设东莞设计公司排名榜
  • dede小说网站模板北京教育云平台网站建设
  • 嘉兴网站建设多少时间深圳设计公司电话
  • 镇江网站seo外包有哪些网站是可以做宣传的
  • 医保局网站建设中标公告长春做公司网站的
  • 莞城做网站扬州国土资源局网站开发区分局
  • 温江网站建设网红营销英文
  • 河北建设教育培训网站ui设计app界面设计流程
  • 做物流的用什么网站配货做任务领佣金的网站源码
  • 外汇期货喊单网站怎么做的嘉兴做网站美工的工作
  • 网站 抄袭佛山网站建设方案书
  • 免费手机端网站模板下载替网站做任务怎么做的
  • 学校门户网站建设的意义网络营销的概念及内容
  • 免费稳定的网站空间外墙清洗
  • 网站备案需要收费么南宁网站建设方案报价
  • asp网站开发工程师如何创建一个网站的流程
  • 主机屋怎么做网站c2c网站制作
  • 手机网站设计神器网页怎么制作二维码
  • 网站开发项目经理岗位职责商城网站 运营
  • 长沙网站优化技巧房地产开发资质
  • 江苏外贸网站建设推广大地资源在线观看视频在线观看
  • 怎样做电影下载网站wap网站如何推广
  • 网站建设需要准备什么信誉好的徐州网站建设
  • 南京做网站南京乐识专业wordpress内存不足