時間限制 2000 ms ・ 記憶體限制 256 MB
題目描述
地鐵網是一棵帶旅行時間的樹。你每年會到若干車站各造訪指定次數，每次都從家出發並返回家，不把多個目的地串成一趟。選擇一個車站當作住處，使全年往返旅行時間最少，並找出所有同樣最佳的車站。
輸入格式
第一行案例數 c（1 ≤ c ≤ 200）。每筆先給 n（1 ≤ n ≤ 50000），再給 n−1 行 a、b、t，表示相鄰車站與旅行秒數（1 ≤ t ≤ 300）。車站編號 1 到 n。接著給目的地數 m（0 ≤ m ≤ n），再給 m 行 a、f，f 為每年造訪次數（1 ≤ f ≤ 500），目的地不重複。
輸出格式
每筆輸出兩行：第一行為最少全年往返秒數，第二行為所有最佳車站編號，遞增排列且以單一空白分隔。
題目來源：UVa 12223 — Moving to Nuremberg，CPE 歷屆試題。 原題：https://onlinejudge.org/external/122/12223.pdf
範例測資
範例輸入 1
2 2 1 2 17 2 1 5 2 10 5 1 3 10 2 3 20 3 4 30 4 5 30 3 1 10 2 10 5 20
範例輸出 1
170 2 3000 3 4 5
請先登入後再提交程式碼
討論與題解
載入討論區…