乘公交,看奧運(yùn)模型的建立與求解.

1、- 1 -乘公交，看奧運(yùn)模型的建立與求解【摘要】本文在對(duì)大量數(shù)據(jù)的分析并結(jié)合乘客乘坐公交車(chē)的心里， 建立了以最小換乘法為基 礎(chǔ)的公交換乘模型。乘客選擇公交出行首先是考慮到公交的舒適性和方便性，其次才會(huì) 考慮時(shí)間和費(fèi)用的最大合理性。因此，本文以最小換乘為首要目標(biāo)建立基本的公交換乘 模型。我們首先想到的是廣度優(yōu)先搜索，即欲查找從起始站點(diǎn)A到目的站點(diǎn)B的最短路徑,可以從A點(diǎn)出發(fā)，以公交車(chē)路線為基礎(chǔ)進(jìn)行廣度優(yōu)先搜索，到B站點(diǎn)即結(jié)束。此時(shí)找 到B站點(diǎn)時(shí)，一定是轉(zhuǎn)車(chē)次數(shù)最少的。在廣度優(yōu)先搜索的基礎(chǔ)上，我們建立了問(wèn)題一的數(shù)學(xué)模型：I)BusA為途徑A站的所有路線的集合，BusB為途徑B站的所有路線的集合。

2、如 果BusABusB式0，說(shuō)明A到B站可以不用轉(zhuǎn)車(chē)就能到達(dá)。直接可以得到A，B站的直達(dá)路線。II)如果BusA BusB-一，再依次從與BusA有公共站點(diǎn)的公交線路BusAi(i為 從A站轉(zhuǎn)乘i次可乘坐的公交路線，i=1,2)中查找是否與BusB有公共路線， 若存在則算法結(jié)束，若不存在則按此步驟繼續(xù)直到查找到為止。III) 如果存在多種方案的轉(zhuǎn)乘次數(shù)相同，則依據(jù)次要目標(biāo)費(fèi)用最少和時(shí)間最短選 取最佳路線。由于實(shí)際生活中人們往往對(duì)轉(zhuǎn)乘次數(shù)有一個(gè)可以承受的范圍，為減少計(jì)算量，本文 中我們假設(shè)轉(zhuǎn)乘次數(shù)為i3則認(rèn)為路線不可達(dá)。對(duì)問(wèn)題二的模型是建立在問(wèn)題一模型的基礎(chǔ)上， 我們把地鐵線路當(dāng)成特殊的公交線

3、并入公交系統(tǒng)， 在路線的選擇上同一規(guī)劃， 仍以最小轉(zhuǎn)乘代價(jià)為首要目標(biāo)， 對(duì)問(wèn)題一的 模型進(jìn)行了合理的修改。問(wèn)題三加入了步行的因素，使得可以乘坐的路線大大增加。步行換乘通常有以下的 兩種類型：1、兩條公交線路相交，但不存在相交的站點(diǎn)，行人需要下車(chē)后步行到鄰近的 站點(diǎn)進(jìn)行換乘。2、兩條公交線路不相交，但兩行車(chē)路線上有相鄰站點(diǎn)，行人選擇下車(chē)步 行到鄰近站點(diǎn)進(jìn)行換乘。如果步行的代價(jià)足夠小，而且可以有效減少換乘次數(shù)，完全可 以把步行考慮進(jìn)路線選擇中?！娟P(guān)鍵詞】公交最佳路線最小轉(zhuǎn)乘法廣度優(yōu)先搜索- 2 -一、 問(wèn)題重述我國(guó)人民翹首企盼的第29屆奧運(yùn)會(huì)明年8月將在北京舉行，屆時(shí)有大量觀眾到現(xiàn)場(chǎng) 觀看奧運(yùn)比賽

4、，其中大部分人將會(huì)乘坐公共交通工具(簡(jiǎn)稱公交，包括公汽、地鐵等) 出行。這些年來(lái)，城市的公交系統(tǒng)有了很大發(fā)展，北京市的公交線路已達(dá)800條以上，使得公眾的出行更加通暢、便利，但同時(shí)也面臨多條線路的選擇問(wèn)題。針對(duì)市場(chǎng)需求， 某公司準(zhǔn)備研制開(kāi)發(fā)一個(gè)解決公交線路選擇問(wèn)題的自主查詢計(jì)算機(jī)系統(tǒng)。為了設(shè)計(jì)這樣一個(gè)系統(tǒng)，其核心是線路選擇的模型與算法，應(yīng)該從實(shí)際情況出發(fā)考慮，滿足查詢者的各種不同需求。請(qǐng)你們解決如下問(wèn)題：1、僅考慮公汽線路，給出任意兩公汽站點(diǎn)之間線路選擇問(wèn)題的一般數(shù)學(xué)模型與算法并根據(jù)附錄數(shù)據(jù)，利用你們的模型與算法，求出以下 線(要有清晰的評(píng)價(jià)說(shuō)明) 。、S3354 S1828(2)、S1557

5、S0481、S000IS0073(5)、S0148S04852、同時(shí)考慮公汽與地鐵線路，解決以上問(wèn)題。3、假設(shè)又知道所有站點(diǎn)之間的步行時(shí)間，請(qǐng)你給出任意兩站點(diǎn)之間線路選擇問(wèn)題的數(shù)學(xué)模型模型假設(shè)1.假設(shè)乘客都能搭上自己想要乘坐的公交車(chē)或地鐵；2.假設(shè)交通順暢，沒(méi)有擁堵現(xiàn)象；3.采用同一站點(diǎn)名的站點(diǎn)均認(rèn)為是同一站點(diǎn)，沒(méi)有空間上的差異；4.假設(shè)公交車(chē)都按時(shí)發(fā)車(chē)、按時(shí)到達(dá)，乘客無(wú)需花費(fèi)多余的時(shí)間等車(chē)；5.假設(shè)整個(gè)公交網(wǎng)絡(luò)是一個(gè)連通圖，任意兩個(gè)站點(diǎn)都有路可達(dá)；6.假設(shè)超過(guò)三次轉(zhuǎn)乘次數(shù)的路線被認(rèn)為是不可達(dá)。SiLiDi三、 符號(hào)說(shuō)明編號(hào)為i的公交站點(diǎn)編號(hào)為i的公交路線編號(hào)為i的地鐵站TMBusALine從

6、源站到目的站花費(fèi)的時(shí)間，單位為分鐘 從源站到目的站花費(fèi)的金錢(qián)，單位為元 途徑A站的所有路線的集合，A為站點(diǎn)名 公交及地鐵線路集合四、問(wèn)題分析乘客出行選擇公交路線時(shí)，首先考慮的是轉(zhuǎn)車(chē)次數(shù)，其次才是路徑的長(zhǎng)度。因?yàn)檗D(zhuǎn) 乘次數(shù)的增加必定會(huì)導(dǎo)致乘車(chē)費(fèi)用的增加，同時(shí)也會(huì)增大時(shí)間的開(kāi)銷(xiāo)，如轉(zhuǎn)乘途中步行 花費(fèi)的時(shí)間，等車(chē)的時(shí)間等等?？臻g上距離最短的路徑，對(duì)于公交乘客來(lái)說(shuō)并不一定是 最合理的路徑。轉(zhuǎn)車(chē)途中各種不確定因素也會(huì)大大增加。乘客往往會(huì)選擇盡量少的轉(zhuǎn)車(chē) 路線以避免各種不必要的麻煩。對(duì)于大多數(shù)選擇公交車(chē)出行的人們來(lái)說(shuō)，盡量少的轉(zhuǎn)車(chē) 次數(shù)才應(yīng)當(dāng)是被首先考慮的，其次才是時(shí)間和費(fèi)用。本文6對(duì)起始站終到站之間的最

7、佳路、S0971S0485、S0087S3676- 3 -也是基于乘客的這種想法，在 尋求最小轉(zhuǎn)乘次數(shù)的基礎(chǔ)上考慮時(shí)間和費(fèi)用的最優(yōu)配置。在附件給出的數(shù)據(jù)中光公交線就有520條，公交站點(diǎn)更是多達(dá)3957個(gè)，如此大的數(shù)據(jù) 量如果用手動(dòng)的方法根本是沒(méi)法完成的。解決問(wèn)題的根本是要有一個(gè)好的算法，借助計(jì) 算機(jī)求解來(lái)實(shí)現(xiàn)乘車(chē)路線的優(yōu)化。傳統(tǒng)的Dijkstra算法求的是從某一站到其他所有站點(diǎn)的最短路徑，因此，要查找A站到B站的最短路線，先要求出A站到其他所有站的最短路線，然后才能在求出的這些線 路中找出到B站的路線。在本題中，我們要求的只是A站到B站的最優(yōu)路線，而花費(fèi)大力 氣求出的A站到其他站的路線都不是我

8、們想要的，可見(jiàn)用Dijkstra算法在求解公交線路時(shí)的效率是非常低的。而Dijkstra算法求出的最短路徑并不一定適合乘客的出行，為了達(dá)到最短路徑的目的，乘客往往要不停的轉(zhuǎn)車(chē)，這樣的結(jié)果是沒(méi)有實(shí)際意義的。因此,Dijkstra算法不適合本題的求解。本文以轉(zhuǎn)乘次數(shù)最少為首要目標(biāo)建立公交路線模型，在滿足最小轉(zhuǎn)乘次數(shù)的條件下 以最少時(shí)間、最少費(fèi)用為次要目標(biāo)進(jìn)行求解。五、模型建立與求解一、模型建立問(wèn)題一：1）問(wèn)題一中只要求出6組站點(diǎn)的最優(yōu)公交轉(zhuǎn)乘路線即可。我們首先考慮直達(dá)的情況，即不需轉(zhuǎn)車(chē)就可到達(dá)目的站。（如圖-1所示）設(shè)BusA為途徑A站的所有路線的集合，BusB為途徑B站的所有路線的集合。 如 果

9、BusA BusB=-，說(shuō)明A到B站可以不用轉(zhuǎn)車(chē)就能到達(dá)。取Line=BusA BusB，只 要計(jì)算經(jīng)過(guò)Line中的路線到達(dá)B站的所有情況， 從中選出最少時(shí)間或最少費(fèi)用的路線 即可。 若BusA BusB=一， 即轉(zhuǎn)入步驟2） 。2）需要經(jīng)過(guò)一次轉(zhuǎn)車(chē)時(shí)BUSAQBUSB=0，設(shè)BusA為所有與BusA有公共站點(diǎn)的 路線的集合，若同時(shí)滿足BusA BusB =-， 說(shuō)明A站到B站只需經(jīng)過(guò)一次轉(zhuǎn)車(chē)就可 到達(dá)。 取Line仁BusA,BusB，依次遍歷Line1中各種情況，找出最優(yōu)解即可。（圖-2）- 4 -3）若BusA nBusB=0，則A到B需轉(zhuǎn)車(chē)2次或2次以上，設(shè)Bus為所有與Bus A有公

10、共站點(diǎn)的路線的集合， 也即BusA2為所有在A站轉(zhuǎn)車(chē)兩次能夠搭乘的公交路線。 同 步驟2） ， 計(jì)算Line2=Bus A2BusB的所有情況，若Line2=0，類似的計(jì)算BusA和Linei （i為轉(zhuǎn)車(chē)次數(shù)），依此類推。如果存在多種選擇，則以時(shí)間和費(fèi)用為第二目標(biāo)進(jìn) 行排除，選出最優(yōu)路線。圖-3問(wèn)題二：?jiǎn)栴}二中把地鐵轉(zhuǎn)乘納入最優(yōu)線路的選擇中，對(duì)問(wèn)題二的求解并不需要重新建立模 型求解，只需在問(wèn)題一的求解出的幾條最優(yōu)線路中考慮，對(duì)模型進(jìn)行適當(dāng)?shù)男薷募纯伞?我們把2條地鐵路線當(dāng)成特殊的公交線并入整個(gè)公交系統(tǒng)中，同樣在滿足最小轉(zhuǎn)乘的基 礎(chǔ)上考慮時(shí)間和費(fèi)用的最優(yōu)，因?yàn)榈罔F與地鐵，地鐵與公交之間的轉(zhuǎn)乘代價(jià)

11、也是相當(dāng)高 的。二、模型的求解問(wèn)題一：為了利用計(jì)算機(jī)求解，我們按照上面的模型和算法設(shè)計(jì)了程序（見(jiàn)附錄）用于計(jì)算 公交線路。所得的結(jié)果分析如下：S335X S1828第1條：S3359L436 S1241L16S1828, T=107分鐘，M=3元S335X S2026S1132S2266S2263S3917S2303S2301S3233S0618S0616S2112S2110S2153S2814S2813S3501S3515S3500S0756S04 92S0903S1768S0955S0480S2703S2800S2192S2191S1829S3649S1784S1241S1784S1828

12、第2條：S3359L436 S1784L167S1828, T=101分鐘，M=3元S3359S2026S1132S2266S2263S3917S2303S2301S3233S0618S0616S2112S2110S2153S2814S2813S3501S3515S3500S0756S0492S0903S1768S0955S0480S2703S2800S2192S2191S1829S3649S1784S1828- 5 -第3條：S3359L436 S2606購(gòu)S1828, T=125,M=3S335X S202 S1132S2266S2263S3917S2303S2301S3233S0618S

13、0616S2112S2110S2153S2814S2813S3501S3515S3500S0756S04 92S0903S1768S0955S0480S2703S2800S2192S2191S1829S3649 S1784S1241S3695S2606S2599S3512S3695S1241S1784S1828第4條：S3359L469S0519L167S1828, T=140,M=4S3359S2026S1132S2265S2654S1729S3766S1691S1383S1381S1321S2019S2017S2159S0772S0485S2385S2810S3189S0964S04 64

14、S0271S0297S1555S0519S1893S3496S1883S3400S1159S1160S0576S0578S3095S0096S0095S1193S0105S1194S1189S2801S0590S1240S1241S1784S1828S3359S2026S1132S2265S2654S1729S3766S1691S1383S1381S1321S2019S2017S2159S0772S0485S2385S2810S3189S0964S04 64S0271S0297S1555S0519S0516S1980S2364S0727S0304S3192S0294S3057S2262S030

15、1S1119S0250S2604S2606S2599S3512S3695S1241S1784S1828第6條：S3359L469S0727L217 S1828, T=137,M=3S3359S2026S1132S2265S2654S1729S3766S1691S1383S1381S1321S2019S2017S2159S0772S0485S2385S2810S3189S0964S04 64S0271S0297S1555S0519S0516S1980S2364S0727S0304S3192S0294S3057S2262S0301S1119S0250S2604S2606S2599S3512S369

16、5S1241S1784S1828S3359S2026S1132S2265S2654S1729S3766S1691S1383S1381S1321S2019S2017S2159S0772S0485S2385S2810S3189S0964S0464S0271S0297S1555S0519S0516S1980S2364S0727S0304S3192S0294S3057S2262S0301S1119S0250S2604S2606S2599S3512S3695S1241S1784S1828第8條：S3359L469S3192L217 S1828, T=137,M=3S3359S2026S1132S2265

17、S2654S1729S3766S1691S1383S1381S1321S2019S2017S2159S0772S0485S2385S2810S3189S0964S04 64S0271S0297S1555S0519S0516S1980第7條:S3359L469 S0304L217S1828, T=137,M=3第5條:S1828, T=137,M=3- 6 -S2364S0727S0304S3192S0294S3057S2262S0301S1119S0250S2604S2606S2599S3512S3695S1241S1784S1828在上面相同轉(zhuǎn)乘次數(shù)的8條線路中我們可以看到費(fèi)用大都是3元，但

18、是第2條線路 上花費(fèi)的時(shí)間最少。所以最優(yōu)路線為S3359- S1784- S1828,T=101,M=3。根據(jù)第一對(duì)起始路線的方法， 我們同理可得其他5對(duì)起始站之間的最佳路線分別為:S1557S0481:S1557L084orL36S1919L417 S2424L254orL312S0481,T=112,M=3(3) S0971S0485- 7 -問(wèn)題二:如果出行時(shí)考慮上地鐵路線，那么我們出行的路線可能會(huì)有新的乘車(chē)路線。根據(jù)假 設(shè)，同一地鐵站對(duì)應(yīng)的任意兩個(gè)公汽站之間可以通過(guò)地鐵站換乘（無(wú)需支付地鐵費(fèi)）。也就是說(shuō)， 你只要花上地鐵的3元票價(jià)就可以在任務(wù)地鐵路線上進(jìn)行換乘， 而不需要花 費(fèi)多余的費(fèi)

19、用。在問(wèn)題一中，我們通過(guò)數(shù)學(xué)建模解決了公交換乘的問(wèn)題，現(xiàn)在我們?cè)?原有公交線路基礎(chǔ)上加入了地鐵線路。我們可以假設(shè)地鐵線路是當(dāng)成是一條新的公交 路線，而把所有地鐵所能到達(dá)的站點(diǎn)連成一體，對(duì)于價(jià)格上只要多出3元。如果不考慮地鐵換乘和行駛的時(shí)間的話，我們可以把地鐵所能到達(dá)的幾個(gè)點(diǎn)當(dāng)成一個(gè)集合點(diǎn)來(lái) 處理。對(duì)于問(wèn)題一中的（1）（3）（4）這三個(gè)一次公交換乘就能解決的出行問(wèn)題，由于出 發(fā)站點(diǎn)和目的站點(diǎn)都不在地鐵線路上。如果我們?cè)诎肼窊Q乘地鐵只是會(huì)增加出行的麻 煩性和價(jià)格，故我們不需要做任何變動(dòng)。對(duì)于（6）來(lái)說(shuō)，S0087在地鐵的D27站,S3676在地鐵的D36站，所以我們可以選擇乘坐地鐵T2,這樣只需要

20、花時(shí)22.5分鐘和3元的 地鐵票價(jià)。對(duì)于問(wèn)題一中的（2）和（5）。這兩種情況屬于二次公交換乘情況，由于這兩種情況的出發(fā)站點(diǎn)點(diǎn)和目的站點(diǎn)都不在地鐵線路上，所以出發(fā)和最后到達(dá)所坐的都必須是 公交車(chē)，則如果要換乘地鐵則要選擇中間的那次換車(chē)?，F(xiàn)在我們來(lái)看幾個(gè)數(shù)據(jù)的比較:相鄰公汽站平均行駛時(shí)間（包括停站時(shí)間）：3分鐘相鄰地鐵站平均行駛時(shí)間（包括停站時(shí)間）：2.5分鐘公汽換乘公汽平均耗時(shí)：5分鐘（其中步行時(shí)間2分鐘）地鐵換乘地鐵平均耗時(shí)：4分鐘（其中步行時(shí)間2分鐘）地鐵換乘公汽平均耗時(shí)：7分鐘（其中步行時(shí)間4分鐘）公汽換乘地鐵平均耗時(shí)：6分鐘（其中步行時(shí)間4分鐘）公汽票價(jià)：分為單一票價(jià)與分段計(jì)價(jià)兩種，標(biāo)記

21、于線路后；其中分段計(jì)價(jià)的票價(jià)為:020站：1元；2140站：2元；40站以上：3元地鐵票價(jià)：3元（無(wú)論地鐵線路間是否換乘）如果僅從價(jià)格上考慮，我們選擇的應(yīng)該是公交路線，因?yàn)榈罔F的價(jià)格為3元，相當(dāng)于分段計(jì)價(jià)公交行駛40站以上的價(jià)格，為公交路線最貴的價(jià)格。所以從金錢(qián)花費(fèi)上來(lái) 考慮的話，二次換乘的過(guò)程中不選擇地鐵。如果從時(shí)間上考慮的話，只選用公交換乘（2）耗時(shí)112分鐘，（5）耗時(shí)100分鐘, 改成地鐵換乘會(huì)增加地鐵與公交，公交與地鐵以及等車(chē)的時(shí)間，相應(yīng)的換乘復(fù)雜度也 會(huì)增加，故不予考慮。L013L417S0971-勺S2184-、S0008S0073S0008L463S2083L057(5)S01

22、48S085:S0418L308S0036L157S0087S3676S0485, T=128,M=3S0073, T=83,M=2S3351L417 S0485, T=100,M=3S3676, T=65,M=2- 8 -問(wèn)題三：加入步行因素現(xiàn)實(shí)生活中，出行時(shí)在選擇行車(chē)路線時(shí)可以通過(guò)在部分站點(diǎn)步行小段距離再轉(zhuǎn)車(chē)以 減少換乘次數(shù)的現(xiàn)象。也就是說(shuō) ，人們轉(zhuǎn)車(chē)的時(shí)候并不是在所下的站點(diǎn)，而是在所下 站點(diǎn)的附近站點(diǎn)換車(chē)的。通常有以下的兩種類型：1兩條公交線路相交，但不存在相交的站點(diǎn)，行人需要下車(chē)后步行到鄰近的站點(diǎn)進(jìn)行換乘。2、兩條公交線路不相交，但兩行車(chē)路線上有相鄰站點(diǎn)，行人選擇下車(chē)步行到鄰近站點(diǎn)進(jìn)行

23、換乘。所以在選擇兩站點(diǎn) 最佳路線的時(shí)候如果需要考慮到現(xiàn)實(shí)情況，則要加入步行因素。步行類型 II根據(jù)這種因素，我們對(duì)我們前面的模型進(jìn)行適當(dāng)?shù)男薷摹?wèn)題一模型中所有的BusA設(shè)為經(jīng)過(guò)A站點(diǎn)及其周邊站點(diǎn)的公交線路的集合， 同理BusB設(shè)為經(jīng)過(guò)B站點(diǎn)及 其周邊站點(diǎn)的公交線路的集合，其余部分同問(wèn)題一的模型。六、模型評(píng)價(jià)和改進(jìn)本題所做的模型完全是建立在數(shù)據(jù)的基礎(chǔ)上，與實(shí)際情況可能存在不一致。在實(shí)際 中，最少換乘數(shù)并不一定是時(shí)間最少或者價(jià)格最省的路線。因?yàn)?，?duì)于公交線路來(lái)說(shuō)， 同樣的兩個(gè)站點(diǎn)在不同的路線中，兩站點(diǎn)之間的站點(diǎn)數(shù)會(huì)不一樣。而且實(shí)際生活中，相 鄰的兩個(gè)站點(diǎn)有可能出現(xiàn)沒(méi)有路線直達(dá)的情況，這時(shí)我們可

24、以選擇步行，這樣對(duì)最少換 乘算法的選擇也會(huì)產(chǎn)生不一致。如果知道一個(gè)城市公交線路的數(shù)據(jù)，同時(shí)得到這些數(shù)據(jù)所形成的實(shí)際路線圖形，我 們可以在圖上畫(huà)出兩站點(diǎn)相連的直線， 通過(guò)圍繞直線附近的行車(chē)路線來(lái)選擇我們換乘的 車(chē)次。同樣，我們可以把出發(fā)站點(diǎn)設(shè)置為圓心，以一定量的時(shí)間或者是金錢(qián)為單位半徑 做出行人可到達(dá)的范圍，通過(guò)對(duì)半徑的依次增加使這個(gè)范圍得到擴(kuò)大，最終包括目的站 點(diǎn)以得到最優(yōu)解。七、參考文獻(xiàn)1李玉芝力源敏，城市公交查詢系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)，地礦測(cè)繪,2006, 22：35- 9 -2王建林,基于換乘次數(shù)最少的城市公交網(wǎng)絡(luò)最優(yōu)路徑算法,經(jīng)濟(jì)地理, 2005年9月：6736763孫湧 基于寬度優(yōu)先遍歷樹(shù)

25、的公交線路換乘算法,深圳職業(yè)技術(shù)學(xué)院學(xué)報(bào), 2004年第4期：10114張帥,彭玉青,趙鎮(zhèn),李志強(qiáng),螞蟻算法在公交查詢最短路徑求法中的應(yīng)用,華中科技大學(xué)學(xué)報(bào)（自然科學(xué)版）, 2003年10月：3133145閆小勇,王揚(yáng),劉海寧,公交乘車(chē)路線查詢中的換乘識(shí)別方法,交通標(biāo)準(zhǔn)化,157期：173174- 10 -附錄：/*主要功能：找經(jīng)過(guò)某一站點(diǎn)的所有公交線路*/ #include #include #include #include #include using namespace std;class Station public: vector vec; string name;Station

26、() Station (const string& name) (*this).name=name;bool operator = (const Station& sta) const return =name;bool operator (const Station& sta) const return ;int main(void) ifstream in(input.txt); ofstream out(output.txt);int i, j, pos=0; string str;Station temp; vector

27、sta; vector:iterator it;int k=0;while (instr) if (str0 = L) +pos;else if (str0 = S)it=find(sta.begin(), sta.end(), Station(str);if (it!=sta.end() if (find(*it).vec.begin(), (*it).vec.end(), pos)=(*it).vec.end() (*it).vec.push_back(pos);else sta.push_back(Station(str); stasta.size()-1.vec.push_back(p

28、os);sort(sta.begin(), sta.end();for (i=0; ista.size(); +i) stai.vec.size()endl;for (j=0; jstai.vec.size(); +j) outstai.vecj ;outendl;return 0;/*主要功能：計(jì)算轉(zhuǎn)0次、1次公交的情況*/#include #include #include #include #include #include using namespace std;- 11 -class Station public:string name;vector vec

29、;bool operator = (const Station& sta) const return =name;bool operator != (const Station& sta) const return !=name;class BusLine public:vector vec;vector arrSta(3960);vector arrBus(525);bool isLink(const Station& sta1, const Station& sta2, int& pos) int i, j;bool

30、flag=false;for (i=0; ista1.vec.size(); +i) for (j=0; jsta2.vec.size(); +j) if (sta1.veci=sta2.vecj) pos=sta1.veci; flag=true; break;if (flag) return true; else return false;bool isLink(const vector& vec1, const vector& vec2, vector& vec) int i;bool flag=false;for (i=0; ivec1.size(); +i)

31、if (find(vec2.begin(), vec2.end(), vec1i)!=vec2.end() vec.push_back(vec1i);flag=true;if (flag) return true;else return false;vector lineChangeToStation(int num) vector vec;int i;for (i=0; iarrBusnum.vec.size(); +i) vec.push_back(arrBusnum.veci);return vec;int distance (int num, string start, string

32、end) vector:iterator it1=find(arrBusnum.vec.begin(), arrBusnum.vec.end(), start);vector:iterator it2=find(arrBusnum.vec.begin(), arrBusnum.vec.end(), end); return abs(it1-it2);int main(void) vector first, last;string start, end, str;int i=1, j=0, k=0, num, num1, num2;ifstream in1(output.txt);while (

33、in1strnum) arrS=str;while (num-) - 12 -in1j; arrStai.vec.push_back(j);+i;in1.close();i=0;ifstream in2(input.txt);while (in2str) if (str0=L) +i;else if (str0=S) if (find(arrBusi.vec.begin(), arrBusi.vec.end(), str)=arrBusi.vec.end()arrBusi.vec.push_back(str);in2.close();int count=0;while (tru

34、e) if (count+!=0) break;- 13 -coutstartend;num1=(start1-48)*1000+(start2-48)*100+(start3-48)*10+(start4-48);num2=(end1-48)*1000+(end2-48)*100+(end3-48)*10+(end4-48);if (isLink(arrStanum1, arrStanum2, i) coutTrueendl;else int Min=INT_MAX;for (i=0; iarrStanum1.vec.size(); +i) first=lineChangeToStation

35、(arrStanum1.veci);for (k=0; karrStanum2.vec.size(); +k) last=lineChangeToStation(arrStanum2.veck);vector temp; if (isLink(first, last, temp) for (j=0; jtemp.size(); +j) num=0; num+=distance(arrStanum1.veci,tempj)*3+distance(arrStanum2.veck, tempj, end)*3+5;couttempj numnum) Min=num;if (Min!=INT_MAX)

36、 coutMin=Minendl; else cout 經(jīng)過(guò)轉(zhuǎn)一次，找不到 endl;return 0;/*主要功能：計(jì)算轉(zhuǎn)兩次公交車(chē)的情況*/#include #include #include #include #include #include using namespace std;/站點(diǎn)class Station public:string name; vector vec;bool operator = (const Station& sta) const return =name;bool operator != (const Station& s

37、ta) const return !=name;/公交線路class BusLine public: vector vec;vector arrSta(3960); vector arrBus(525);/判斷兩條公交路線是否相連bool isLink(const Station& sta1, const Station& sta2, vector& vec) int i, j;bool flag=false;for (i=0; ista1.vec.size(); +i) for (j=0; jsta2.vec.size(); +j) if (sta1.

38、veci=sta2.vecj) vec.push_back(sta1.veci), flag=true; break;start,- 14 -if (flag) return true;else return false;/計(jì)算兩站的距離int distance (int num, string start, string end) vector:iteratorit1=find(arrBusnum.vec.begin(),arrBusnum.vec.end(),start);vector:iterator it2=find(arrBusnum.vec.begin(), arrBusnum.vec.end(), end); return abs(it1-it2);int main(void) vector first, last; string start, end, str;int i=1, j=0, k, num, num1, num2, sum, min;ifstream in1(output.txt);while (in1strnum) arrS=str;while (num-) in1j; arrStai.vec.