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

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

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

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

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

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

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

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

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

9、apj, 1, mapj, 2, mapi, 1, mapi, 2)*t ; if umi n 若該費(fèi)用為最小，則記下最小費(fèi)用和去往城市then begin min；Jmui Jj end；then end；then for jJ4*no-3w to 4*now do搜索第二組內(nèi)城市 now 的每一個(gè) 機(jī)場(chǎng) j if not usedj then begin計(jì)算出發(fā)城市至機(jī)場(chǎng)i，然后坐火車至機(jī)場(chǎng)j的最小 費(fèi)用u J an si+dist(mapj, 1, mapj, 2, mapi, 1, mapi, 2)*f now ; if umin若該費(fèi)用為最小，則記下最小費(fèi)用和去往城市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的每一個(gè) 機(jī)場(chǎng) jif not usedj then beg in計(jì)算出發(fā)城市至機(jī)場(chǎng)i，然后坐飛機(jī)至機(jī)場(chǎng)j的最小 費(fèi)用u J an si+dist(mapj, 1, mapj, 2, mapi, 1, mapi, 2)*t ; if umi n 若該費(fèi)用為最小，則記下最小費(fèi)用和去往城市then beg in minjuij; end; then end； then end； then if mi in 4*b- 3.4*b若到達(dá)目標(biāo)城市的一個(gè)機(jī)場(chǎng),則輸出最小費(fèi)用并退出程 序then begin writeln(min:0:2); exit; endthen else begin否則置 mi 機(jī)場(chǎng)進(jìn)入第一組,并記下出發(fā)城市至該機(jī)場(chǎng)的 最小