#include<stdio.h>
#include<stdlib.h>
#define LEN 60
#define MAX 1000
int main()
{
int i, j;
int P, R;
int mp[LEN][LEN];
scanf("%d", &P);
while(P != 0)
{
scanf("%d", &R);
for(i = 0; i < LEN; i++)
for(j = 0; j < LEN; j++)
mp[i][j] = MAX;
int a, b, len;
for(i = 1; i <= R; i++)//read road
{
scanf("%d%d%d", &a, &b, &len);
if(len < mp[a][b])
{
mp[a][b] = mp[b][a] = len;
}
}
int s[LEN] = {0};
int cost[LEN];
int lenall = 0;
s[1] = 1;//init
for(i = 1; i <= P; i++)
cost[i] = mp[1][i];
for(i = 1; i <= P - 1; i++)//prim
{
int t = 1;
int min = MAX;
for(j = 1; j <= P; j++)
if(s[j] == 0 && cost[j] <= min)
{
t = j;
min = cost[j];
}
s[t] = 1;
lenall += min;
for(j = 1; j <= P; j++)//updat cost[]
if(s[j] == 0 && mp[t][j] < cost[j])
cost[j] = mp[t][j];
}
printf("%d\n", lenall);
scanf("%d", &P);
}
//system("pause");
}
posted on 2012-08-07 10:47
小鼠標 閱讀(132)
評論(0) 編輯 收藏 引用 所屬分類:
圖論