/*
4
1 2 1 1 1 2 0 1
1 3 4 0 (1代表费用为0) 1 3 4 0
1 4 1 1 ======> 1 4 0 1
2 3 3 0 2 3 3 0
2 4 2 1 2 4 0 1
3 4 5 0 3 4 5 0
最小生成数 ：
1、具有树的结构，在无向图中不能形成闭环
2、必须全部节点都要连上
*/
#include<iostream>
using namespace std;
int n, m; //节点，节点的度
int x, y;
int z;
int dist[101];
int cost[101][101];
int visit[1001];
int sum;
int dis;
int main()
{
sum = 0;
cin >> n; //输入节点数
for (int i = 1; i <= n; i++)//初始化二维数组
{
for (int j = 1; j <= n; j++)
{
cost[i][j] = 999999; //每个都等于 “无穷”
}
}
int m = n * (n - 1) / 2; //节点的度的最大数量
while (m--) //判断每条路是否已修
{
cin >> x >> y >> dis >> z;
if (z == 0)//如果路是未修，将dis存入数组
cost[x][y] = cost[y][x] = dis;
else//若路已修，dis为0
cost[x][y] = cost[y][x] = 0;
}
for (int j = 1; j <= n; j++)//将第一个点到另外的点的dis存入dist
{
dist[j] = cost[1][j]; //存放距离的大小
}
visit[1] = 1;
dist[1] = 0;
for (int i = 1; i <= n; i++)
{
int mindis = 999999, k = 0; // 999999代表无穷，说明两地不通路
for (int j = 1; j <= n; j++)
{
if (visit[j] == 0 && dist[j] < mindis) // 费用不为0 且 通路
{
mindis = dist[j];
k = j;
}
}
visit[k] = 1;
if (k != 0)//如果k！= 0，说明图上有点 没有被连接
{
sum += dist[k];
for (int j = 1; j <= n; j++)
{
if (visit[j] == 0 && dist[j] > cost[k][j])
{
dist[j] = cost[k][j];//更新dist
}
}
}
}
cout << sum << endl;
return 0;
}
这个是用cost二维数组存储花费， dist存放距离，用动态规划的方法来寻找最小花费的距离
您好，我是有问必答小助手，您的问题已经有小伙伴解答了，您看下是否解决，可以追评进行沟通哦~
如果有您比较满意的答案 / 帮您提供解决思路的答案，可以点击【采纳】按钮，给回答的小伙伴一些鼓励哦～～
ps: 问答会员年卡【8折】购 ，限时加赠IT实体书，即可 享受50次 有问必答服务，了解详情>>>https://t.csdnimg.cn/RW5m