#include 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"<>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; }