【題26】Car的旅行路線--試題解析

1、題 26】Car 的旅行路線 又到暑假了，住在城市 A的Car想和朋友一起去城市B旅游。她知道每個 城市都有四個飛機場，分別位于一個矩形的四個頂點上，同一個城市中兩個機 場之間有一條筆直的高速公路（圖 629）。第i個城市中高速公路的單位里程價格為 Ti,任意兩個不同城市的 機場之間均有航線，所有航線單位里程的價格均為 t。 圖 6.2.9 那么Car應如何安排到城市B的路線才能盡可能的節(jié)省花費昵？她發(fā)現(xiàn)這 并不是一個簡單的問題,于是她來向你請教。 任務 找出一條從城市A到B的旅游路線，出發(fā)和到達城市中的機場可以任意選 取,要求總的花費最少。 輸人文件： 鍵盤輸入文件名 輸出： 到屏幕（輸出最

2、小費用,小數(shù)點后保留 2位。） 輸入格式 第一行為一個正整數(shù)n（0 n 1,0表示有n組測試數(shù)據(jù)。 每組的第一行有四個正整數(shù) s, t, A, B。 s （0v S 10）表示城市的個數(shù)，t表示飛機單位里程的價格，A, B分別為 城市A, B的序號，（1A BS。 接下來有s行，其中第i行均有7個正整數(shù)x i1 , y i1，x i2，y i2，x i3，y i3，T i，這當中的(x i1， y 11) ， (x i2， y 12) ， (x i3， y 13) 分別是第i個城市中任意三個機場的坐標，T i 為第 i 個城市高速公路單位里程的價格。 輸出格式： 共有 n 行，每行一個數(shù)據(jù)對應

3、測試數(shù)據(jù)。 輸入輸出樣例 輸入 13 10 1 3 輸出 47.55 題解 1. 計算兩點間的歐氏距離 2/ 7 輸入信息給出了各城市內(nèi)高速公路單位里程價格和城市間飛機的單位里程 價格。要知道兩個機場間的路程費用，必須知道兩個機場間的距離。設兩個機 場的坐標分別為（x 1, y 1）和（x 2, y 2）。按照22 歐氏公式，它們之間的距離應為dist=（x 1 x 2） （y 1 y 2）。我們通過函數(shù)dist（x1，y1，x2，y2）計算和返回（x 1, y 1）和（x 2, y 2）間的歐氏距離： function dist（x1，y1，x2，y2:integer）: real ； 計算

4、和返回（x1，y1）與（x2，y2）間的歐氏距 3使用Dijkstra算法計算最小費用 按照Dijkstra算法的思想，將所有機場分為兩組 第一組： 包括已確定最小費用的機場； 第二組： 包括尚未確定最小費用的機場；設true used為機場的分組標志。其中 usedi二false 機場i在第一組 機場i在第二組 ans為第一組機場的最小費用序列。其中an si為出發(fā)城市至第一組中機場i 的最小費用（1 i 4*n 我們按最小費用遞增的順序把第二組的機場加到第一組中去，直至到達目 標城市b中的任一個機場為止。 在這個過程中，總保持從出發(fā)城市 a到第一組各機場的最小費用都不大于 從a至第二組任何

5、機場的費用。 另外，每一個機場對應一個費用值。第一組機場對應的費用值就是由a到 此機場的最小費用；第二組機場對應的費用值就是a經(jīng)由第一組機場（中間機 場）至此機場的最小費用。具體作法是： 初始時，出發(fā)城市a的四個機場進入第一組（useda*4-3、useda*4-2、 useda*4-1、useda*4設為true）;所有機場的費用值為0;第二組包含其它所 有機場。 然后每次從第二組中選一個機場 mi加到第一組中。這個機場必須滿足如下 條件： 5出發(fā)城市a經(jīng)由第一組的某機場i（usedi=true）可直達mi機場； 6其費用（ansi+機場i至機場mi的直接費用）在第二組機場的所有費用中 是最

6、小的；機場i至機場mi使用的交通工具不同，直接費用亦隨之不同。問題 是機場i至機場mi究竟使用哪一種交通工具。這取決于兩個機場所屬城市的關 系： 機場i所屬的城市為now二i 1 1。 4 若機場mi在城市now (4*now-3 mi4*noW，則從機場i坐火車至機場 mi; 若機場 mi在其他城市(K mi4*noWt, 4*now+1 mi4*n，則從機場i坐 飛機至機場mi。 按照上述規(guī)律依次往第一組加入一個機場mi，直至被加入的機場 mi屬于目 標城市b為止(4*b-3 mi4*b。 由此得出算法： procedure solve; var used: array 1.4*maxn

7、of boolean ; 第一組的機場標志min, u: real; 目前為止的最小費用為 min，當前方案的費用為umi, i, j, now: integer ； 被加入第一組的機場序號為 mi，機場所在的城市序號為 no wbegi n if a=b若出發(fā)城市即為目標城市，則輸出最小費用為 0,并退出程序then beginwriteln (0); exit; end; then fillchar(used, sizeof(used), false); 初始時所有機場在第二組，該組內(nèi)所有 機場的最小費用為0 5 / 7 fillchar(ans，sizeof(ans)，0)； useda

8、*4-1 J true 出發(fā)城市a的四個機場進入第一組useda*4-2 J true useda*4-3 J true useda*4 Jtrue repeat min J maxi nt; 最小費用初始化for i J1 to 4*n do 搜索第一組內(nèi)的每一個機場 if usedi then begin nowJ(i-1) div 4 +1；計算機場 i 所在的城市序號 for j J1 to 4*n-o4wdo 搜索第二組內(nèi)城市1城市now-1的每一個機場jif not usedj then begin計算出發(fā)城市至機場i，然后坐飛機至機場j的最小 費用u J an si+dist(m

9、apj, 1, mapj, 2, mapi, 1, mapi, 2)*t ; if umi n 若該費用為最小，則記下最小費用和去往城市then begin min；Jmui Jj end；then end；then for jJ4*no-3w to 4*now do搜索第二組內(nèi)城市 now 的每一個 機場 j if not usedj then begin計算出發(fā)城市至機場i，然后坐火車至機場j的最小 費用u J an si+dist(mapj, 1, mapj, 2, mapi, 1, mapi, 2)*f now ; if umin若該費用為最小，則記下最小費用和去往城市then beg

10、in min J;um i Jj; end; then end; then for j J4*now+1 to 4*n do搜索第二組內(nèi)城市 now+j城市n的每一個 機場 jif not usedj then beg in計算出發(fā)城市至機場i，然后坐飛機至機場j的最小 費用u J an si+dist(mapj, 1, mapj, 2, mapi, 1, mapi, 2)*t ; if umi n 若該費用為最小，則記下最小費用和去往城市then beg in minjuij; end; then end； then end； then if mi in 4*b- 3.4*b若到達目標城市的一個機場,則輸出最小費用并退出程 序then begin writeln(min:0:2); exit; endthen else begin否則置 mi 機場進入第一組,并記下出發(fā)城市至該機場的 最小