回分類題庫
d066: 4.網路設計
關鍵字: 103年台中區複賽

測資點 : 2 | Time Limit : 1000 ms | Memory Limit : 32000 KB
Accepted : 72 Times / 63 Users | Submit : 211 Times / 68 Users | Accepted rate : 93%
題目加入時間 : 2015-09-07 14:53

Content: 简体中文

某一城市欲建立都會網路,以使每一城市均可連線到其他各城市(可能直接連線或透過其他的城市間接連線)。假設任兩個城市之間的佈線成本為已知(有些城市之間已知無法佈線,其佈線成本可視為無限大);每一條網路線均為雙向傳送。請寫一程式,印出哪些城市之間需要施工佈線,以找出此城市使用最低成本完成此都會網路之佈線架構。 

Input:

輸入資料的內容如下:第一列有兩個正整數n及m,其中n代表城市個數(n<=10),m代表有m個可能的佈線連結兩城市。第二列有n個字串,代表n個城市代碼(代碼最多5個字元)。其後有m列,每一列之資料依序為兩城市代碼,及連接此兩城市之佈線成本。各項資料之間以一個空白分隔;佈線成本為一正整數。

Output:

印出二列。第一列為佈線架構,印出數組資料,每一組資料為兩個城市代碼,代表此兩個城市需要施工佈線,每一組資料包含在一對括號之中。第二列為佈線總成本。各項資料之間以一個空白分隔。

註:為方便 Online Judge 的判斷,輸出的資料必須為唯一的形式,因為輸出的第一行可能有許多不同的組合,故增加以下兩點規則:

  1. 每組城市代碼依照輸入資料第二行的輸入順序,例如C1為1、C2為2以此類推,比較前面的優先輸出 。
  2. 各組城市代碼請以第一個城市代碼的順序輸出,第一個城市的代碼相同時,再以第二個城市的代碼順序輸出。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
6 9
C1 C2 C3 C4 C5 C6	
C1 C2 1
C1 C4 7
C2 C3 3
C2 C4 6
C2 C5 4
C3 C5 5
C3 C6 9
C4 C5 3
C5 C6 8

Sample Output :

(C1 C2)(C2 C3)(C2 C5)(C4 C5)(C5 C6)
19

Hint :

Author :

103年台中區複賽 (管理員:sagit)

  Solve it!   Status Forum