g006. 最小延遲網路規劃 - 海青資訊科選手補給站

內容

你是一位網路工程師，負責規劃公司內部網路的最小延遲設計。公司有 𝑁 個伺服器節點，以及若干條光纖通道，每條通道有不同的延遲時間（以毫秒 ms 為單位）。你的任務是計算全網路中節點的連接方式，使總延遲時間達到最小，並確保所有伺服器相互連通。

如下圖所示，節點 1 到 2 的通道延遲時間為 3，節點 3 到 4 的通道延遲時間為 2，節點 4 到 3 的通道延遲時間為 6，依此類推。
若以陣列 𝑥[𝑖][𝑗] 表示節點 𝑖 到 𝑗 的通道延遲時間，則 𝑥[1][2]=
3，x[1][2]=3，𝑥[3][4]=2，𝑥[4][3]=6。若某值為 −1，表示兩節點間無直接通道連接。

上述例子之網路拓樸圖表示為：
int x[4][4] = {{0, 3, 2, 3},{-1, 0, 5, 3},{-1, 5, 0, 2},{7, 2, 6, 0}};

輸入說明

第一列輸入 n（節點數量）。
第二列開始，共 𝑛 列，每列輸入 𝑛 個整數（以空白隔開），表示節點間的通道延遲時間。若兩節點間無直接通道，輸入
−1。
(註：2≤ n≤100，通道延遲訊息範圍： 1 ~ 100)

輸出說明

找出節點間的最小通道延遲連接，使整個網路互相連通。
輸出格式為 i j c，表示節點 i 到 j 的通道延遲時間 𝑐。
輸出順序按 i 值升序排列，若 i 值相同，則按 j 值升序排列。每條連接記錄換行輸出。
最後一列輸出網路中所有通道延遲時間總和。
若節點間，只要有一節點無法與其他節點連通，則輸出 -1。

範例輸入 #1

範例輸出 #1

範例輸入 #2

4
0 1 -1 -1
2 0 -1 6
-1 5 0 -1
-1 -1 -1 -1

範例輸出 #2

範例輸入 #3

4
0 3 -1 -1
2 0 -1 -1
-1 -1 0 -1
-1 5 -1 0

範例輸出 #3

-1

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (16%): 1.0s , <1K
公開測資點#1 (16%): 1.0s , <1K
公開測資點#2 (17%): 1.0s , <1K
公開測資點#3 (17%): 1.0s , <1K
公開測資點#4 (17%): 1.0s , <1M
公開測資點#5 (17%): 1.0s , <1M

提示：

標籤:

演算法

出處:

海青工商資訊科 [管理者： zero(管理員) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」