7-13|7-13 公路村村通 (30分)
现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。
输入格式:
输入数据包括城镇数目正整数N（≤1000）和候选道路数目M（≤3N）；随后的M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从1到N编号。
输出格式:
输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出?1，表示需要建设更多公路。
输入样例:
6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3
输出样例:
12#include
#define INFINITY 65535
using namespace std;
const int maxn=1001;
int dist[maxn], C[maxn][maxn], parent[maxn];
int N, M, cnt;
int findMin(){
int minn=INFINITY, index=-1;
for(int i=1;
i<=N;
i++){
if(dist[i]!=0&&minn>dist[i]){
minn=dist[i];
index=i;
}
}
return index;
}
void Prim(int s){
int cnt=1, Totalcost=0;
for(int i=1;
i<=N;
i++){
parent[i]=s;
//记录父节点 （路径）
dist[i]=C[s][i];
}
parent[s]=-1;
dist[s]=0;
int v;
while(1){
v=findMin();
if(v==-1)break;
Totalcost+=dist[v];
cnt++;
dist[v]=0;
//收录后dist的值要变为0，表明该结点v已被收录
for(int i=1;
i<=N;
i++){
if(dist[i]!=0&&C[v][i] 【7-13|7-13 公路村村通 (30分)】
推荐阅读
- 2020-7-13晨间日记
- 2019-07-13Anaconda（转载的别人的）
- Python求解谷歌高速公路招聘广告（{|Python求解谷歌高速公路招聘广告：{ 无理数e中前十位连续的素数 }.com）
- 诗◇夜明
- 百里画卷草原天路|百里画卷草原天路 -- 中国的66号公路
- 走完美国西海岸的这条路线，加州的一号公路就不用去了
- javascript|全国交通智慧升级，阿里云视频上云打造高速公路“视觉中枢”
- 今起南京对市域公路通道全面开展疫情防控检查
- 2018-07-13宜接纳
- 7-13|7-13 说反话-加强版 (12分)（附详细教程）