#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#define LEN 510
#define MAX 100000
int main()
{
int i, j;
int N, E;
int A, B, K;
int T;
int mp[LEN][LEN];
scanf("%d", &T);
while(T--)
{
scanf("%d%d", &N, &E);
for(i = 0; i < LEN; i++)
for(j = i; j < LEN; j++)
mp[i][j] = mp[j][i] = MAX;
for(i = 0; i < E; i++)//read map
{
scanf("%d%d%d", &A, &B, &K);
mp[B][A] = mp[A][B] = K;
}
int s[LEN] = {0};
int cost[LEN];
int lenall = 0;
s[0] = 1;
for(i = 0; i < N; i++)
cost[i] = mp[0][i];
for(j = 0; j < N - 1; j++)
{
int t = 0;
int min = MAX;
for(i = 0; i < N; i++)
if(s[i] == 0 && cost[i] <= min)
{
t = i;
min = cost[i];
}
s[t] = 1;
lenall += min;
for(i = 0; i < N; i++)
if(s[i] == 0 && mp[t][i] < cost[i])
cost[i] = mp[t][i];
}
printf("%d\n", lenall);
}
//system("pause");
}
posted on 2012-08-07 11:23
小鼠標(biāo) 閱讀(128)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
圖論