本文最后更新于 1163 天前，其中的信息可能已经有所发展或是发生改变。
代码语言：javascript复制#include<iostream>
using namespace std;
#define INF 100000
int sumweight=0;
int arr[100][100];
int lowcost[100];
int nearvex[100];
int n,m;
void f(int v0){
for(int i=0;i<n;i ){
lowcost[i]=arr[v0][i];
nearvex[i]=v0;
}
nearvex[v0]=-1;
cout<<v0<<"--";
for(int i=0;i<n-1;i ){
int MIN=INF;
int v=-1;
for(int j=0;j<n;j ){
if(nearvex[j]!=-1&&MIN>lowcost[j]){
v=j;
MIN=lowcost[j];
}
}
if(v!=-1){
cout<<v<<"--";
sumweight =lowcost[v];
nearvex[v]=-1;
for(int j=0;j<n;j ){
if(nearvex[j]!=-1&&arr[v][j]<lowcost[j]){
lowcost[j]=arr[v][j];
nearvex[j]=v;
}
}
}
}
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i ){
for(int j=0;j<n;j ){
if(i==j){
arr[i][j]=0;
}else{
arr[i][j]=INF;
}
}
}
for(int i=0;i<m;i ){
int x,y,v;
cin>>x>>y>>v;
arr[x][y]=v;
arr[y][x]=v;
}
f(0);
cout<<endl<<sumweight;
return 0;
}Post Views: 251
