今天的問題是關于圖形結(jié)構(gòu)的，但是如果各位愿意的話，BFS也應該可以做。

點開下面的音樂，開啟今天的內(nèi)容吧！

今天的題目是一個基本的dijkstra圖形數(shù)據(jù)題。代碼量中等，其實使用廣度優(yōu)先也是可以做出來的，搜索量初步估計相差不大（要是估摸不準，也就差一兩個數(shù)量級，“問題不大”），具體題目如下

H 城是一個旅游勝地，每年都有成千上萬的人前來觀光。為方便游客，巴士公司在各個旅游景點及賓館，飯店等地都設置了巴士站并開通了一些單程巴士線路。每條單程巴士線路從某個巴士站出發(fā)，依次途經(jīng)若干個巴士站，最終到達終點巴士站。

一名旅客最近到 H 城旅游，他很想去 S 公園游玩，但如果從他所在的飯店沒有一路巴士可以直接到達 S 公園，則他可能要先乘某一路巴士坐幾站，再下來換乘同一站臺的另一路巴士，這樣換乘幾次后到達 S 公園。

現(xiàn)在用整數(shù)?1,2,…,N?給 H 城的所有的巴士站編號，約定這名旅客所在飯店的巴士站編號為?1，S 公園巴士站的編號為?N。

寫一個程序，幫助這名旅客尋找一個最優(yōu)乘車方案，使他在從飯店乘車到 S 公園的過程中換車的次數(shù)最少。

初步看這個題，我想，這不就是地圖導航干的事情嗎？于是我到洛谷上一查才發(fā)現(xiàn)，這原來是1997年的OI題······

上古老題了?。《宜尤活A測到了現(xiàn)代的地圖的導航技術，這就真的很神奇了。

對于這道題而言，一大難點就在于輸入的方法。相信大家向來最討厭這種長度提前不說并且不固定的輸入，關鍵還都是數(shù)據(jù)！這就要求我們能夠去從數(shù)據(jù)和空格的混雜體中提取有用的數(shù)據(jù)出來，并且轉(zhuǎn)化到數(shù)組里面?zhèn)溆?。我個人就是在這一點被卡死的······

輸入數(shù)據(jù)的時候我從某個大牛那里學到了一招：先將前面的兩個m和n用cin或者scanf進行輸入，再寫一個getline，這樣的話我們就可以在輸入數(shù)據(jù)后放心回車啦！

再輸入線路信息的時候，我的方案是就開一個字符串，然后將字符串信息轉(zhuǎn)化成圖形數(shù)據(jù)結(jié)構(gòu)（鄰接矩陣）進行存儲，然后再次輸入，再轉(zhuǎn)化，以此直到輸入完所有的數(shù)據(jù)為止。

具體的建圖方法是：把一條線路的每一個站點都和該站前面的所有站點建立有向邊，得到一個可以模擬城市公交系統(tǒng)的圖。

但是，我的踩坑點就在數(shù)據(jù)的轉(zhuǎn)化上。

當測評機輸入完了一行路線數(shù)據(jù)后，接下來的字符是什么?這個我是不知道的。但是我覺得這個格子一定是'\0'或者'? '之一，但是事實卻真的不是這樣的，于是乎我就爆0了。

解決方案是將我在上圖程序中畫出來的判定機制進行一些改變，從要求改字符不是\0或者空格改成只能是數(shù)字類型的數(shù)據(jù)，這樣就很好的解決了這個問題。如改成line[t]<='9'&&line[t]>='0';

存圖的時候由于這道題里面的公交線路存在重疊的問題，所以鄰接表的使用就會很困難，從我個人的感覺看，鄰接矩陣是明顯更好的選擇。如果鄰接表不判重就會憑空增加計算量。這就很不劃算了（但是說實在話，我個人覺得鄰接表在遍歷時會稍微快一點，訪問一條邊用鄰接表就很慢）

存完圖，就是一個非?；镜膁ijkstra了。我們在鄰接表中只需要把有連接的邊設置為1，其他部分設置為0x3f3f3f3f就可以正常進行計算了。

最后提醒一點：輸出的時候數(shù)據(jù)一定-=1，因為我們實際上算的是乘坐公交的次數(shù)，換車次數(shù)就是乘坐次數(shù)減去1。遇上0x3f就輸出NO，意味著坐車到不了。

最后，呈現(xiàn)一下我的代碼

今天的文章就到這里啦！記得三連哦~