1226 . H遊戲
TopCoder
Tags
Description
你有玩過H-Game嗎？我知道一定沒有，因為大家都這麼正派，怎麼可能會去玩呢XD
有一天，無聊的Sana買了 T 款H-Game，他很好奇在不存檔的情況下(即每次想走一條新的路線都要從頭開始)，走完每一個女主角的所有路線各需要花多少時間。他已經去了某個神秘的網站查好遊戲裡面女主角的資料跟整個遊戲的路線圖，每一款H-Game裡面有 N 個女主角(1<=N<=100)，V 個分支點(包含起點跟各女主角的終點, N+1<=V<=1,000)，E 個事件(E<=1,000,000)，每個事件都會花費一些時間。由於Sana蒐集完這些資料以後就已經累的半死，而且好死不死他還知道你會寫程式，於是他便請你來幫他寫個程式計算看看到底每個女主角要花多少時間才能把全部的路線走完。身為Sana好友的你能夠幫助他嗎？
Input Format
第一行會有一個正整數 T 代表Sana買了幾套H-Game。
每款H-Game的資料的第一行有三個正整數 N, V, E 分別代表女主角的個數、分支點的個數、事件的個數。
接下來的 N 行每一行代表一個女主角的名字。女主角的名字都是由大寫或小寫的英文字和數字組成，而且長度都會不會超過20個位元組。
最後的 E 行每行有三個數字 X, Y, Z 分別代表一個事件的起點、終點跟花費時間。
分支點的編號是由 0 到 V-1，第0號代表起點，第 i 號(1<=i<=N)則代表第 i 個女主角的結局。
Output Format
每款H-Game依照輸入的順序輸出 N 行代表要玩完這些女主角的所有路線所要花費的時間。
你可以假設Sana在玩遊戲時作選擇的時間可以忽略不計，另外由於這個答案可能會很大，
所以你只需要告訴Sana答案除以32768的餘數就可以了，畢竟如果時間要花很久的話Sana也不可能照著玩下去吧？
Sample Input 1
2 6 6
Kotomi
Kaoru
0 3 3
0 5 2
3 4 7
3 1 5
4 1 6
5 2 4
1 2 1
Yuu
0 1 99
Sample Output 1
Kotomi: 24
Kaoru: 6
Game #2
Yuu: 99
Hints
就第一組測試資料來說，女主角有兩個(Kotomi跟Kaoru)，分支點有6個，事件有6個。
Kotomi的路線有兩條，第一條是0->3->1，第二條是0->3->4->1。所需要花費的時間為(3+5)+(3+7+6)=24。
Kaoru的路線只有一條：0->5->2，所需要花費的時間為2+4=6。
※Tmt說：噢，你可以假設Sana買的遊戲裡不會有無限多種路線。
Problem Source
原TIOJ1226 / TIOJ 2008例行賽03-Elite (prob H)。Problem Setter：akira。
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 50 |
| 2 | 1 | 50 |