回分類題庫
d032: 2008 程式達人 F - 戰略城市
出處:

Difficulity : 2
Accepted : 9 Times | Submit :23 Times | Clicks : 1509
Accepted : 7 Users | Submit : 8 Users | Accepted rate : 88%
Time Limit :2001 ms | Memory Limit : 32001 KBytes
題目加入時間 : 2008-10-10 10:26

Content :

「宇宙侵略軍特殊先鋒部隊」(簡稱 Keroro 小隊)由 Keroro 軍曹領軍,準備潛入愛爾普藍星。為了擬定進攻戰略,Keroro小隊先分析愛爾普藍星上各大城市的重要性。但隊員之間對於重要性的定義,卻有不同的看法。

  1. Keroro 認為越多公路交會的城市就越重要。
  2. Kururu 則根據愛爾普藍星人善用 Google Map 的習慣,認為愛爾普藍星人到各大城市都會選擇最短的路線。因此,Kururu 認為重要的城市往往會是在兩兩城市間的最短路線所路經之處。
  3. Tamama 則認為越重要的城市,與其他城市的平均最短距離就會越短。

例如:假設愛爾普藍星上有五個城市A, B, C, D, E彼此都有公路連通,其長度如上圖所示。由上圖可以得知,
AB 間的最短路線為 A→B,長度為 2
AC 間的最短路線為 A→B→C,長度為 5
AD 間的最短路線為 A→B→D,長度為 3
AE 間的最短路線為 A→E,長度為 5
BC 間的最短路線為 B→C,長度為 3
BD 間的最短路線為 B→D,長度為 1
BE 間的最短路線為 B→A→E,長度為 7
CD 間的最短路線為 C→B→D,長度為 4
CE 間的最短路線為 C→B→A→E,長度為 10
DE 間的最短路線為 D→B→A→E,長度為 8
因此,

  1. Keroro 認為這五個城市的重要性排名為:A>B=C=D>E,因為 A, B, C, D, E 分別有 4, 3, 3, 3, 1 條公路交會。
  2. Kururu 則認為這五個城市的重要性排名為:B>A>C=D=E,因為 B 是 5 對城市最短路線的路經之處,A 則是 3 對城市最短路線的路經之處,而其他城市都沒有出現。
  3. Tamama 則認為這五個城市的重要性排名為:B>A>D>C>E,因為 B, A, D, C, E 到其他城市的最短路線之平均長度為13/4, 15/4, 16/4, 22/4, 30/4。
已知,
  1. 愛爾普藍星人到其他城市旅行時,如果兩條路線長度相同,根據愛爾普藍星人的習俗,會選擇路線上所有城市代碼的英文字母順序總和最小的路線。例如:如果有兩條路線 A→B→D→C 與 A→Z→C 的總長度相同,愛爾普藍星人會選擇路線 A→B→D→C,因為路線 A→B→D→C 的字母順序總和為 1+2+4+3=10,而 A→Z→C 的字母順序總和為 1+26+3=30。
  2. 愛爾普藍星上的公路都是雙向的。

請協助 Keroro 小隊將城市的重要性由大而小排列。若重要性相同,則根據城市代碼的英文字母順序,順序小的排在前面。

Input :

由檔案輸入,輸入的資料包括二部分
  1. 城市數目:一個整數 n,1 ≤ n ≤ 26
  2. 公路基本資料: m 行記錄,1 ≤ m ≤ n ×(n-1)/2。每行記錄包括三個欄位,欄位之間以一空白字元隔開。第一個與第二個欄位是城市代碼,都是大寫英文字母。第三個欄位是一個介於 1~100 的整數。

Output :

輸出資料包括三部分,分別為 Keroro, Kururu, Tamama 的城市重要性排名。若重要性相同,則根據城市代碼的英文字母順序,順序小的排在前面。每一部分都有 n 行,每一行是城市代碼。

Sample Input :

5
A B 2
B D 1
A C 10
A E 5
B C 3
A D 6
D C 5

Sample Output :

A
B
C
D
E
B
A
C
D
E
B
A
D
C
E

Hint :

解題率:0/19

Author :

(管理員:MrWrongAnswer)

  Solve it!   Status Forum (0)

C++
C
JAVA
36827. nothinglo (4 ms , 421KB)
36825. MK (6 ms , 421KB)
51276. uglyman (8 ms , 426KB)
36826. MK (8 ms , 422KB)
31585. henryokc (8 ms , 398KB)
55348. ag100 (1 ms , 250KB)
29532. onedie (6 ms , 340KB)
沒有解題記錄

執行時間會受很多因素影響因此僅供參考,主機等級請看這裡