#include<bits/stdc++.h> |
using namespace std; |
int M[1002][1002], Dist[1002], TF[1002]; |
void tree( int N) |
{ |
int k, sum=0 ,i ,j; |
for ( i = 2; i <= N; i ++) //把所有与顶点1相邻的边放入Dist数组 |
Dist[i] = M[1][i]; |
TF[1] = 1; |
for ( i = 0; i < N-1; i ++) |
{ |
int min1 = 9999, k = -1; |
for ( j = 1; j <= N ; j ++) |
{ |
if ( !TF[j] && Dist[j] < min1) //如果当前道路未被经过且权值小于当前最小的权值 |
{ |
min1 = Dist[j]; //更改最小权值数值 |
k = j; //记录最小全职的下标 |
} |
} |
if ( k == -1 ) //如果K的下标还是-1,说明没有通向该村庄的道路 |
{ |
cout<< "Impossible" <<endl; |
return ; |
} |
TF[k] = 1; //记录该条道路已经过 |
sum += min1; |
for ( j = 1; j <= N; j ++) |
{ |
if ( !TF[j] && M[k][j] < Dist[j] ) |
Dist[j]=M[k][j]; |
} |
} |
cout<<sum<<endl; |
} |
int main() |
{ |
int N, m, i, j; |
while (cin>>N>>m) |
{ |
for ( i = 1 ;i <= N ; i ++) |
{ |
Dist[i] = 9999; |
TF[i] = 0; //所有道路都标志为未经过 |
for ( j = 1; j <= N ; j ++) |
M[i][j] = 9999; //所有道路权值初始化为无穷大 |
} |
for ( i = 0 ; i < m ; i ++) //输入有权无向图的邻接矩阵 |
{ |
int a, b, c; |
cin>>a>>b>>c; |
M[a][b] = c; |
M[b][a] = c; |
} |
tree(N); |
} |
return 0; |
} |
by: 发表于:2017-12-13 10:32:31 顶(0) | 踩(0) 回复
??
回复评论