Problem 11015 05-2 Rendezvous，小組集合

此題給你兩整數，N 和 M，接下來會有 N 列姓名，代表組員 1 ~ N 的姓名。再接下來會有 M 列資料，M 列每列會有三整數 i, j 和 k，代表組員 i 到組員 j 的距離為 k。最後要你求出哪一組員的家，與其他所有組員家的距離是最短的。

使用「佛洛依德最短路徑演算法」就可以解決此題。首先，創建一個 N * N 陣列 W 並且將陣列內所有值歸 0，順便紀錄 N 個組員的姓名；而接下來 M 列資料，讀取每行 i, j , k 後將 W[i][j] = W[j][i] = k。

因為可能有些組員到其他組員家是沒有路勁的，所以演算法稍做修改，C 語言程式碼如下：

#define SIZE 23
struct Crew
{
    char name[12];
};
struct Crew c[SIZE];
int W[SIZE][SIZE];

主程式內 ....
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;
            }
        }

最後，加總以某組員家為集合地點的路徑，再去比較誰的路徑最短，最後再印出組員名字。C 語言程式碼如下：

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

By David.K

p11015題目連結
回ACM題庫目錄
回首頁