戰事將起，亞拉岡將如何應付
你們一定聽過托爾金的著名小說"魔戒"，就如你所知道的一樣，魔戒最終被佛羅多(Frodo Baggins)投入末日火山(mountain of doom)而被摧毀，因此邪惡的索倫(Sauron)得不到魔戒終於潰不成軍。擊退索倫中土終於恢復了和平，亞拉岡(Aragorn)登基成為國王，從此過著幸福快樂的日子。
然而這並不是故事真正的結束，擊敗索倫並非戰勝了邪惡取得最終的勝利，因為索倫的主子，邪惡的黑暗君主魔茍斯(Morgoth)，將從黑暗深淵中復活。
索倫死後多年，亞拉岡已經年邁，而他的兒子艾達瑞安(Eldarion)成為新的國王。和平的日子持續不了多久，有一天他們發現黑暗君主魔茍斯已經蘇醒，並計畫統治世界。整個中土世界即將狼煙再起。
艾達瑞安與老臣們商討許多阻止魔茍斯的計劃，他們有中土世界的地圖，所以他們知道中土世界內有許多領地，各領地之間有多條道路相互連接，他們知道每條聯絡道路的旅程有多久，從一領地到另一領地之間有一到多種路途程的選擇，每一領地都可藉由聯絡道路通往其他所有的領地。
這就是為什麼他們會如此害怕魔茍斯大軍的原因，因為一旦魔軍佔領了任一領地之後就可以肆無忌憚地侵略所有其他的領地，為了阻擋魔軍的去路，他們派來佇守各個道路的軍隊數量將十分可觀。
艾達瑞安與他的父親都是極重視榮譽的男人(man of honor)，所以他並不希望任一領地疏於防備，但是他的軍隊數量比魔茍斯的軍隊還少，這使他居於劣勢。如果他都把軍隊派佇到各個聯絡道路的話，他也許會有勝算，但將會有不少領地被攻佔。如果他們選擇派軍隊佇守各個領地的話，萬一有任何領地被攻陷，那其他領地就更危險了，因為魔軍可以利用沒有守備的道路來調度軍隊，更有甚者，箝制各領地之間的溝通並一一擊破。又如果艾達瑞安同時派軍隊防守各道路與各領地的話，會因為各據點兵力太少而無力抵抗魔苟斯的大軍。
經過漫長的討論，始終找不到兩全之計，所以艾達瑞安向他的父親亞拉岡尋求協助，亞拉岡花了一天的時間思考，隔天告訴艾達瑞安他的計劃，計劃是在讓軍隊調度不受影響的情況之下(各領地之間皆可出兵到其他任一領地)，維持最少的聯絡道路，其他多餘的道路會被摧毀，因為他們有很多投石機可以不費吹灰之力就把道路截斷。
然後，他們還需要選出最先可能被攻擊的領地，這些領地會由作戰經驗豐富的亞拉岡來選出，並稱這些領地為"主要領地(prime territories)"。所有軍隊只會被派佇到這些主要領地，當任一領地遭受攻擊的時候(不論是否是主要領地)，該領地上的傳訊者會到各個有兵力佇守的主要領地尋求協助，傳訊者會隨機地並且一一地選擇各主要領地進行通報，直到所有主要領地都出兵相助，傳訊者總是會選擇尚未被通報的主要領地尋求協助。因此，到達一個領地的"途程時間(the estimated time)"被定義為所有主要領地到達該領地所需時間之總合，而"總途程時間(total estimated time)"定義為所有領地的"途程時間"之總合。你可以忽略傳訊的時間。
現在，他們決定採用亞拉岡的主意，所以他們要留住使總途程時間最小的道路，而你是其中一位參謀，你對地圖瞭若指掌，現在你必須找出最小的總途程時間。記住，中土世界的存亡就掌握在你的手中。
Input
輸入資料的第一列為T(<=100)，表示有幾組測試資料。每組測試資料以一列空行開頭，接著下一列有三個整數 n (2 <= n <= 16), m 及 k (1 <= k <= n)，n是領地個數，m是道路個數，k是主要領地個數，領地的編號為從0到(n-1)。下一列共有k個以空白隔開的整數，每個整數用來表示主要領地的編號。再接下來的m列每列有三個整數u, v (0 <= u, v < n , u != v) 及 w (1 <= w <= 1000)
，表示有一條聯絡領地u到領地v的雙向道路，並且該道路的途程時間為w分鐘。你可以假定所有的道路都是有效的，不會出現重複的道路，且任兩個領地之間的道路最多只會有一條。
Output
針對每組測試資料，印出測試資料編號與最小總途程時間(the minimum Total estimated time)。
Sample Input | Sample Output |
2 3 2 1 0 0 1 2 1 2 5 3 3 2 0 2 0 1 2 1 2 5 0 2 50 | Case 1: 9 Case 2: 21 |
沒有留言:
張貼留言