【JAVA】无向连通图到达所有点必须经过固定点成本之和的最小值(Pro20210903)(Dijkstra + DP)
2021/9/8 11:06:04
本文主要是介绍【JAVA】无向连通图到达所有点必须经过固定点成本之和的最小值(Pro20210903)(Dijkstra + DP),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
【JAVA】无向连通图到达所有点必须经过固定点成本之和的最小值(Pro20210903)(Dijkstra + DP)
- 题目
- 思路
- 代码
题目
略
思路
每次到达下一个点必须经过1号店,可以拆解为从当前点到1号点的最短路径,加上从1号点到目的地的最短路径。
也就是说,整个过程可以分解为:
1号点到剩余所有点:在下面会包含,不用单独列举(计算)
2号点到剩余所有点:【2 --> 1 --> 3 --> 1 --> 4 --> 1 --> 5… --> N-1 --> 1 --> N】
3号点到剩余所有点:--------------【3 --> 1 --> 4 --> 1 --> 5… --> N-1 --> 1 --> N】
4号点到剩余所有点:----------------------------【4 --> 1 --> 5… --> N-1 --> 1 --> N】
…
N-1号点到剩余所有点:--------------------------------------------------【N-1 --> 1 --> N】
可以观察出:
过程中均为1号点和其它点的路程
且:
【1 --> 2】或【2 --> 1】最短路径使用次数:1
【1 --> 3】或【3 --> 1】最短路径使用次数:2
…
【1 --> N-1】或【N-1 --> 1】最短路径使用次数:N - 2
【N --> 3】或【N --> 1】最短路径使用次数:N - 1
则:
- 使用Dijkstra,求出1号点到所有点的最短路径COST(无向图,也就是所有点到1号点的最短路径);
- 遍历1号点到所有点的最短路径,对于i点,ASW += (i - 1) * COST[i];
- ASW即为所求。
代码
import java.io.BufferedReader; import java.io.FileInputStream; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; import java.util.PriorityQueue; import java.util.StringTokenizer; public class Main { static int T, N, M; static ArrayList<Edg>[] DATA; // 原始数据 static long COST[], ASW; public static void main(String[] args) throws Exception { System.setIn(new FileInputStream("D:\\SW\\TestCase\\sample_input_20210813.txt")); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; int T = Integer.parseInt(br.readLine()); for (int tc = 1; tc <= T; tc++) { st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); COST = new long[N + 1]; ASW = 0L; DATA = new ArrayList[N + 1]; for (int i = 1; i <= N; i++) DATA[i] = new ArrayList<>(); // 邻接链表读入边、权值数据并存储 for (int i = 0; i < M; i++) { st = new StringTokenizer(br.readLine()); int from = Integer.parseInt(st.nextToken()); int to = Integer.parseInt(st.nextToken()); long cost = Long.parseLong(st.nextToken()); DATA[from].add(new Edg(to, cost)); DATA[to].add(new Edg(from, cost)); } // 迪杰斯特拉求最短路径 dijkstra(); for (int i = 2; i <= N; i++) ASW += (i - 1) * COST[i]; System.out.printf("#%d %d\n", tc, ASW); } } static void dijkstra() { boolean visited[] = new boolean[N + 1]; // 已求得最短路径的点标记为true int visitedCount = 0; // 已求得最短路径的点个数 // 按当前到达点的成本升序排序 PriorityQueue<Edg> pq = new PriorityQueue<>(new Comparator<Edg>() { @Override public int compare(Edg o1, Edg o2) { return Long.compare(o1.cost, o2.cost); } }); pq.add(new Edg(1, 0L)); // 设定起点为1号点 while (!pq.isEmpty()) { Edg now = pq.poll(); // 获取当前到达的点 if (visited[now.point]) // 当前点的最短路径已求得 continue; // 更新当前点的最短路径,并标记 visited[now.point] = true; COST[now.point] = now.cost; if (++visitedCount == N) // 所有点的最短路径已求得 break; // 遍历当前点的连接点 for (Edg next : DATA[now.point]) { if (visited[next.point]) // 若当前节点的最短路径已经确定 continue; // 则松弛操作 if (COST[next.point] < now.cost + next.cost) { COST[next.point] = now.cost + next.cost; visited[now.point] = true; pq.add(new Edg(next.point, now.cost + next.cost)); } } } } static class Edg { int point; long cost; public Edg(int p, long cost) { this.point = p; this.cost = cost; } } }
这篇关于【JAVA】无向连通图到达所有点必须经过固定点成本之和的最小值(Pro20210903)(Dijkstra + DP)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行