ACM 11015 - 05-2 Rendezvous

#include <stdio.h>
#include <memory.h>
#define SIZE 23
struct Crew
{
    char name[12];
};
struct Crew c[SIZE];
int W[SIZE][SIZE];

int main()
{
    int n, m, caseNum = 1, i, j, k, min, minID;
    while (scanf("%d %d", &n, &m) == 2 && n)
    {
        memset(W, 0, sizeof(W));  
        for (i = 1; i <= n; i ++)
            scanf("%s", c[i].name);
        while (m --)
        {
            scanf("%d %d %d", &i, &j, &k);
            W[i][j] = W[j][i] = k;
        }
        
        for (k = 1; k <= n; k ++)
            for (i = 1; i <= n; i ++)
                for (j = 1; j <= n; j ++)
                {
                    if (i != j && W[i][k] != 0 && W[k][j] != 0)
                    {
                        int m = W[i][k] + W[k][j];
                        if (W[i][j] == 0) W[i][j] = m;
                        else if (m < W[i][j]) W[i][j] = m;
                    }
                }
    
        for (i = 1, min = 0; i <= 1; i ++)
            for (j = 1; j <= n; j ++)
                if (i != j)
                    min += W[i][j];
        minID = 1;
        int count;
        for (i = 2; i <= n; i ++)
        {
            for (j = 1, count = 0; j <= n; j ++)
            {
                if (i != j)
                    count += W[i][j];
            }
            if (min > count)
                min = count, minID = i;
        }
        printf("Case #%d : %s\n", caseNum ++, c[minID].name);
        
    }
    return 0;
}

回目錄
回首頁