Problem 341 Non-Stop Travel，不停的旅行

此題給你一個 n 值代表有幾個節點，再來有 n 行代表 1 ~ n 節點與其他節點單向通道的長度，所以每行一開頭，會有一個 m 值代表此節點共與 m 節點有單向通道。接下來會有 m 個 i、j 值，i 代表節點， j 代表長度。舉例：
2
1 2 4
0
此輸入例子代表 1 節點有一單向通道到 2 節點且長度為 4，而 2 節點沒有任何通道。
最後它會給你兩數字 a 和 b，請你印出 a 到 b 的最短路徑以及路徑經過的節點。

這題要用到「佛洛依德最短路徑演算法」，但須稍微修改一下，須先把陣列先建構出來，以上面例子需建構成：

索引\索引 | 1 | 2 |
---------------------
        1 | 0 | 4 |
---------------------
        2 | 0 | 0 |

再使用「佛洛依德最短路徑演算法」，並且用 p 陣列記錄路徑，關鍵程式碼如下：

for (k = 1; k <= n; k++)
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            if (i != j && region[i][k] != 0 && region[k][j] != 0)
            {
                int m = region[i][k] + region[k][j];
                if (region[i][j] == 0)
                    region[i][j] = m, p[i][j] = k;
                else if (m < region[i][j])
                    region[i][j] = m, p[i][j] = k; 

要求出路徑經過的節點，使用以下函式即可印出：

void path(int q, int r)
{
    if (p[q][r] != 0)
    {
        path(q, p[q][r]);
        printf(" %d", p[q][r]);
        path(p[q][r], r);
    }
}

最後只需在主程式這樣呼叫：

printf("Case %d: Path = %d", caseNum ++, i);
path(i, j);
printf(" %d; %d second delay\n", j, region[i][j]);

演算法雖辛苦學了兩個月，但用起來還真能解決很多題目。
By David.K

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