時間限制 1000 ms ・ 記憶體限制 256 MB
題目描述
N 個物品之間有對稱距離矩陣，兩個不同物品的距離為正。請將所有物品恰好分成 K 個非空組，每個物品只屬於一組。分組的品質是所有「不同組」物品對之間的最小距離。求可達到的最大品質；同組物品對不參與最小值計算。
輸入格式
第一行為 N、K，2 ≤ K ≤ N ≤ 500。接著 N 行，每行 N 個整數 D[i][j]，0 ≤ D[i][j] ≤ 10^8。保證對角線為 0，且 i≠j 時 D[i][j]=D[j][i]>0。
輸出格式
輸出最大的最小組間距離。
範例測資
範例輸入 1
3 2 0 2 1 2 0 3 1 3 0
範例輸出 1
2
範例輸入 2
5 3 0 5 6 1 3 5 0 3 4 2 6 3 0 4 7 1 4 4 0 5 3 2 7 5 0
範例輸出 2
3
請先登入後再提交程式碼
討論與題解
載入討論區…