TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

91.7% (11/12)

Submission's AC Ratio

37.8% (14/37)

Tags

Description

  事情發生在跑跑卡恩車大賽後的幾個月…(請參考TIOJ-1022)

  經過了跑跑卡恩車大賽後,原本居住在上城的寒酸員外老姜跟原本居住在下城強大的科學家老皮與老灝成為了好朋友,感情好到常常聚在一起打賭(賭友是嗎?)
  有一天老姜邀請老皮與老灝一同到家裡作客,並在信中誇耀自己有多有錢,比魏晉的石崇當年使用紫絲屏障還奢華,可以讓自己踩著絲製地毯(卡恩國由於天氣關係不適合養蠶等產絲動物,所以價錢十分昂貴)遍遊他所居住的小鎮中所有的觀光景點,老皮與老灝十分懷疑,於是發明了『絲製布料偵測鞋』(就說是強大的科學家咩),並前往老姜家中。

  當老姜看到老灝與老皮提著那雙『絲製布料偵測鞋』過來時,他的心涼掉了半截,他哪有這麼多錢呢?於是沒有辦法,只能能省則省了!
  身為老姜家會計的你,為了拯救老姜的信用,也為了家裡的開銷,決定自己找出如何才能花費最少的錢完成任務(畢竟老姜年紀大了,腦袋不好信任),於是你上網查了地圖跟一些相關資料,所以你知道:

1.老姜住的小鎮名叫做正派鎮(不是真新鎮),是個面積宛如大國般的小鎮(卡恩國國土十分廣闊,就連一個小鎮也可以很大很大),而且住在那兒的人都非常正派,絕對不糟糕。
2.正派鎮中有n個觀光景點,各有各的名字。(1<=n<=50)
3.正派鎮中有m條路,連接兩個觀光景點,各有名字以及長度。
4.觀光景點上會有可愛的服務小妹妹幫你在觀光手冊上蓋章,所以老灝與老皮可以知道你到底有沒有到那裡。
5.由於老灝與老皮太過強大,『絲製布料偵測鞋』不可能出錯,所以只要腳一踏到非絲製布料時,老灝與老皮馬上就會知道。
6.由於卡恩國國庫十分充足,所以觀光景點上總是覆滿著絲製地毯,但是也沒有富有到哪裡去,所以並沒有將道路鋪設地毯。
7.最近物價上漲,原本一單位長度只要66TMT幣的地毯,居然漲到了100TMT幣(TMT幣的幣值非常非常高)
8.老姜祖先還滿有錢的,所以他住在某一個觀光景點上的別墅。
9.我們翻閱地圖發現景點與道路的名稱都不會超過30個字元

但是由於道路實在過於錯綜複雜,所以你決定寫個程式來找出最好的方法!
寫完之後,你就可以幫助老姜脫離困境了!

Input Format

輸入有多筆資料。
當n等於0時,代表輸入結束,聰明的你當然不會對他輸出任何資料。

每一筆資料的:
第1行共有一個數字n,代表觀光景點的個數(由0編號到n-1)
第2行~第n+1行,每行共有一個字串(代表編號n-1的觀光景點的名稱)
第n+2行共有一個數字m,代表道路的個數
第n+3行~第n+m+2行,每行各有一個字串及三個數字,分別代表道路的名稱、道路的兩端以及長度。
第n+m+3行,每行共有一個字串,代表老姜住的景點的名稱。

Output Format

每筆資料若有k條路需要鋪地毯,則輸出k+1行。
前k行輸出被選中的道路,輸出時按照道路輸入順序輸出,連接的兩點,以編號小者優先輸出。輸出格式如下:

#K Road is named A, connect B and C,length=L

K為第K條被選中的道路名稱為A,連接B與C兩個景點,路徑長度為L。
第k+1行則輸出共花了多少TMT幣,格式如下:

Jiang will spend K TMTdollars.

亦即老姜花了K TMTdollars。

Sample Input 1

6
Leaf
Clannad
One
Key
Kanon
Air
10
SayuriRoad 0 1 5
MaiRoad 0 2 10
ShioriRoad 1 2 6
HRoad 1 3 11
NayukiRoad 1 4 16
FateRoad 2 3 14
MakotoRoad 2 5 18
NanohaRoad 3 4 21
LRoad 3 5 33
AyuRoad 4 5 19
Leaf

0

Sample Output 1

#1 Road is named SayuriRoad, connect Leaf and Clannad,length=5
#2 Road is named ShioriRoad, connect Clannad and One,length=6
#3 Road is named HRoad, connect Clannad and Key,length=11
#4 Road is named NayukiRoad, connect Clannad and Kanon,length=16
#5 Road is named MakotoRoad, connect One and Air,length=18
Jiang will spend 5600 TMTdollars.

Hints

對應於範例輸出的地圖如下:

※2007/12/16 SampleI/O格式修正。
※2009/11/15 I/O格式修正,感謝 yuscvscv。

Problem Source

原TIOJ1162 / 96 TWN Practice Contest 4。Problem Setter:hallogameboy。

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1