時間限制 2000 ms ・ 記憶體限制 256 MB
題目描述
鐵路網由數條雙向路線組成，每條路線依序列出車站，相鄰站間行車時間固定 2 小時，轉線不耗時。出現在至少兩條路線的車站稱為重要站。Krochanska 位於某重要站，使他到其餘重要站的最短旅行時間平均值最小。若有多個最佳站，選編號最小者。
輸入格式
第一行為測試筆數。每筆先給站數 N（N ≤ 10000）與路線數 S（S ≤ 100），站編號 1 至 N。接著 S 行，各行依序給一條路線的車站，最後以 0 結束。重要站數介於 1 與 100，所有站之間皆有路徑。
輸出格式
每筆輸出 Krochanska is in: X，其中 X 為答案車站編號。
來源：UVa 11792 — Krochanska is Here!。本敘述依原題規格重新撰寫。
範例測資
範例輸入 1
4 13 3 1 2 3 4 5 6 7 0 8 9 4 10 13 0 11 2 12 9 6 7 0 6 2 2 5 3 6 1 4 0 4 1 6 3 5 2 0 5 2 1 2 3 4 5 0 3 5 1 4 2 0 7 2 3 5 1 2 4 7 6 0 3 6 1 0
範例輸出 1
Krochanska is in: 9 Krochanska is in: 3 Krochanska is in: 4 Krochanska is in: 6
請先登入後再提交程式碼
討論與題解
載入討論區…