百度收录不到我的网站,中信建设有限责任公司官网首页,网站高端,北京网站制作工具最小生成树prim算法 题源#xff1a;代码随想录卡哥的题 链接#xff1a;https://kamacoder.com/problempage.php?pid1053 时间#xff1a;2025-04-18 难度#xff1a;4⭐ 题目#xff1a;
1. 题目描述#xff1a;
在世界的某个区域#xff0c;有一些分散的神秘岛屿代码随想录卡哥的题 链接https://kamacoder.com/problempage.php?pid1053 时间2025-04-18 难度4⭐ 题目
1. 题目描述
在世界的某个区域有一些分散的神秘岛屿每个岛屿上都有一种珍稀的资源或者宝藏。国王打算在这些岛屿上建公路方便运输。
不同岛屿之间路途距离不同国王希望你可以规划建公路的方案如何可以以最短的总公路距离将所有岛屿联通起来。
给定一张地图其中包括了所有的岛屿以及它们之间的距离。以最小化公路建设长度确保可以链接到所有岛屿。
输入描述
第一行包含两个整数V和EV代表顶点数E代表边数。顶点编号是从1到V。例如V2一个有两个顶点分别是1和2。
接下来共有E行每行三个整数v1v2和valv1和v2为边的起点和终点val代表边的权值。
输出描述
输出联通所有岛屿的最小路径总距离
输入示例
7 11 1 2 1 1 3 1 1 5 2 2 6 1 2 4 2 2 3 2 3 4 1 4 5 1 5 6 2 5 7 1 6 7 1
输出示例
6
2. 解题方法
采用prim算法来求最小生成树的问题使用贪心的思想即在循环每一个顶点的过程中寻找与当前生成树距离最近的顶点然后将其加入进来然后更新当前生成树到剩余顶点的最近距离。总共分为3个步骤
寻找初始起点(这里随机即可选择第1个)然后判断剩余节点中与当前生成树距离最近的顶点将其加入生成树更新第2步新增节点到最小生成树后当前其他节点到最小生成树的距离。
3. 代码如下
import java.util.*;
public class Main{ public static void main(String[] args){ Scanner scannernew Scanner(System.in); int vscanner.nextInt();int escanner.nextInt();int[][] gridnew int[v1][v1];for(int i0;iv;i){Arrays.fill(grid[i],10001);}for(int i0;ie;i){int ascanner.nextInt();int bscanner.nextInt();int cscanner.nextInt();grid[a][b]c;grid[b][a]c;}int[] minDistnew int[v1];Arrays.fill(minDist,10001);boolean[] inTreenew boolean[v1];for(int i1;iv;i){int cur-1;int minValInteger.MAX_VALUE;for(int j1;jv;j){if(!inTree[j]minDist[j]minVal){minValminDist[j];curj;}}inTree[cur]true;for(int j1;jv;j){if(!inTree[j]grid[cur][j]minDist[j]){minDist[j]grid[cur][j];}}}int res0;for(int i2;iv;i){resminDist[i];}System.out.println(res);}}
4. 心得体会
算法真的好难呀555~ 有没有路过的大佬分享一下怎么学算法呀~
5. 碎碎念
东b管院本科生-东b计科水硕- 一名热爱技术但菜菜的女生持续前进中~ 如果有技术上的问题分享或者生活中的碎碎念愿意多一个互联网搭子的话: dd19898852196(weiChat)
