#include<stdio.h>
#include<stdlib.h>

const int MAX =0x7fffffff;
int lowcost[110];
int g[110][110];
int visited[110];

void init(int n)
{
    int i;
    int j;
    for(i = 1;i <= n; i++){
        lowcost[i] = 0;
        visited[i] = 0;
    }
    for(i = 1; i <= n; i++){
        for(j = 1; j <= n; j++)
            g[i][j] = MAX;
        g[i][i] = 0;
    }

}

int getmin(int a, int b){
    if(a > b)
        a = b;
    return a;
}

int main()
{
    int n;
    int m;
    int i;
    int j;
    int k;
    int x;
    int y;
    int dis;
    int min;
    int ans;
    while(1){
        scanf("%d", &n);
        if(!n)
            break;
        scanf("%d", &m);
        if(!m){
            printf("0\n");
            continue;
        }
        ans = 0;
        init(n);
        while(m--){
            scanf("%d%d%d", &x, &y, &dis);
            if(!g[x][y])
                g[x][y] = g[y][x] = dis;
            else
                g[y][x] = g[x][y] = getmin(dis, g[x][y]);
        }
        for(i = 2; i <= n; i++)
            lowcost[i] = g[1][i];
        visited[1] = 1;
        for(j = 2; j <= n; j++){
            min = MAX;
            for(i = 1; i <= n; i++){
                if(!visited[i] && lowcost[i] < min){
                    min = lowcost[i];
                    k = i;
                }
            }
            ans += min;
            visited[k] = 1;
            for(i = 1; i <= n; i++){
                if(!visited[i] && lowcost[i] > g[k][i])
                    lowcost[i] = g[k][i];
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

• Re:无上水题！！！！！！！！ (1824) fnoichzhe 2017-12-24 12:33:34