在哪里做网站设计,深圳网站的建设,温州企业网站制作,进入网站空间题目描述 有n个城市#xff0c;其中有些城市之间可以修建公路#xff0c;修建不同的公路费用是不同的。现在我们想知道#xff0c;最少花多少钱修公路可以将所有的城市连在一起#xff0c;使在任意一城市出发#xff0c;可以到达其他任意的城市。 输入 输入包含多组数据其中有些城市之间可以修建公路修建不同的公路费用是不同的。现在我们想知道最少花多少钱修公路可以将所有的城市连在一起使在任意一城市出发可以到达其他任意的城市。 输入 输入包含多组数据格式如下。 第一行包括两个整数n m代表城市个数和可以修建的公路个数。(n 100 m 10000) 剩下m行每行3个正整数a b c代表城市a 和城市b之间可以修建一条公路代价为c。 输出 每组输出占一行仅输出最小花费。示例输入 3 2
1 2 1
1 3 1
1 0示例输出 2
0提示 #includeiostream #includecstring #includecstdio #includecstdlib #define INF 0x3f3f3f3f using namespace std; int arr[110][110];//记录顶点之间的弧关系 int dis[110];//用来记录当前生成树到每个节点的距离权值 bool vis[110];//标记数组 int prim(int n)//生成最小树求最小权值 { memset(vis,false,sizeof(vis));//标记数组清零 for(int i1;in;i) dis[i]arr[1][i];;//从1号节点开始生成树 int ans0;//距离权值总和 vis[1]true;//生成树的根起点标记访问过 for(int i2;in;i)//要生成n-1条边所以循环n-1次 { int posi;//用来记录每一次循环找到的结点编号 int minINF;;//标记为无穷大 for(int j1;jn;j)//对dis数组进行遍历找到距离最小的 if(vis[j]falsedis[j]min) { mindis[j];//更新最小距离 posj;//记录节点编号 } ansmin;//加上找到的最小权值 vis[pos]true;//标记找到的该点被访问 for(int j1;jn;j)//更新dis数组 if(vis[j]falsedis[j]arr[pos][j])//路径通过中间路径pos使路径更小。 dis[j]arr[pos][j];//更新生成树到该点的距离 } return ans; } int main() { int n,m; while(~scanf(%d%d,n,m)) { for(int i1;in;i) for(int j1;jn;j)//边的初始化 { if(ij) arr[i][j]0; else arr[i][j]INF;//无穷大 } for(int i1,v1,v2,w;im;i) { scanf(%d%d%d,v1,v2,w); if(arr[v1][v2]w||arr[v2][v1]w)//选取权值最小的边 arr[v1][v2]arr[v2][v1]w; } printf(%d\n,prim(n)); } }
