1、圖論習題（A 層次）題 1 單詞源程序名可執行文件名輸入文件名輸出文件名words.? (PAS, words.exe words.inwords.outP)Io 和 Ao 在玩一個單詞。他們輪流說出一個僅包含元音字母的單詞，并且后一個單詞的第一個字母必須與前一個單詞的最后一個字母一致。開始。可以從任何一個單詞任何單詞說兩遍，中只能使用給定詞典中含有的單詞。的復雜度定義為中所使用的單詞的長度總和。編寫程序求出使用一本給定的詞典來玩這個所能達到的最大可能復雜度。輸入 words.in輸入文件的第一行包含一個自然數N，1N16，N 表示一本字典中包含的單詞數量。以下的每一行包含字典中的一個單詞，每

2、一個單詞是由字母 A、E、I、O 和U 組成的一個字符串，每個單詞的長度將小于等于 100，所有的單詞是不一樣的。輸出 words.out輸出文件僅有一行包含該的最大可能復雜度。樣例 words.in 5IOO IUUO AI OIOOIAOOIwords.out16題 2starhder 的旅游源程序名可執行文件名輸入文件名 輸出文件名Travel.? (PAS, Travel.exe Travel.inTravel.outP)starhder 突發奇想，要去 G 地，于是他搞來了一張地圖，看怎么走才好。地圖上有很多城市，G 地也是一座城市。每兩座城市之間都可能有直達方法，也有可能兩座城市之

3、間并不能直接相通，而要通過其他的城市轉達。對于兩個城市之間的直達方法，需要一定的時間，當然，如果從 A 城市到 B 城市的直達方法需要T 時間，那么從 B 城市到 A 城市的直達方法也是 T 時間。starhder 想要用最短的時間到達 G 地，但是有個問題，他發現，地圖上有些城市對他很有。所以他要在經過這些城市的基礎上時間最短。starhder 已經用 1、2、3、4、5n 標記了他可能經過的城市（1 代表出發地，n 代表G 地），但是眼花繚亂的地圖讓他感到煩惱。他請你來解決這個問題，時間到達 G 地。輸入輸入文件的第一行是三個正整數 n 和 m，t，n 表示總共有多少個城市（包括出發地和

4、G地），城市數不會超過 200 個；m 是城市的直達路線數（1=m=20000），t 表示一定去的城市數 0=t=10（不包括出發地和 G 地）。接下來一行有 t 個整數，表示一定要去的城市。接下來 m 行，每行包含三個正整數，前兩個數表示分別代表一個城市，第三個數是這兩個城市之間的直達時間。直達時間不會超過 1000000。輸出輸出一個數，題目要求的得最短時間。樣例 Travel.in 5 10 22 31 2 5最小需要多少3 4 743 5 424 5 61Travel.out27題 3jou.? (PAS,旅游路線(jou)源程序名P)可執行文件名 jou.exejou.injou.o

5、ut輸入文件名輸出文件名在 Byand 有 n 個城市（從 1 到 n），它們之間通過雙向的道路相連。Byand的國王并不大方，所以，那里只有 n 1 條道路，但是，它們的連接方式使得從任意城市都可以走到其他的任何城市。一天，starhder 到了為 k 的城市。他計劃從城市 k 開始，游遍城市 m1，m2，m3，mj （不一定要按這個順序旅游）。每個城市 mi都是不同的，并且，也與 k 不同。Starhder 就像每一個旅行家一樣，攜帶的錢總是有限的，所以，他要以最短的路程旅行完所有的城市（從城市 k 開始）。于是，他請你幫助計算一下，旅游完上述的城市最短需要多少路程。輸入第一行包含兩個整數，上文中的 n 和 k，以一個空格隔開。（2= n =50000，1 = k=n）下面的 n 1 行每行描述一條路，第 i + 1 行包含 3 個整數 ai，bi，di，相鄰兩個數用一個空格隔開（1= ai,bi = n，1= di = 1000），ai 和 bi 是用道路直接相連的城市di 是這條道路的長度。第 n + 1 行包含一個整數 j，是 starhder 要旅游的城市數（1= j = n - 1），接下來，一行包含 j 個不同的整數m1，m2，mj，每兩個相鄰的整數用一個空格隔開，表示starhder 想要去