2010年9月17日 星期五

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;
}


回目錄
回首頁

沒有留言 :

張貼留言

Related Posts Plugin for WordPress, Blogger...