# include & ltiostream & gt
# include & lt字符串& gt
# include & ltvector & gt
# include & lt地圖& gt
使用命名空間std
#定義景點4 //自定義景點數量為4個，以後可以擴充。
類景點//景點信息，以後可以擴展。
{
公共:
Sight(string name，string SD){ sname = name；sight _ detial = sd}
string Sight _ Name(){ return sname；}
string Sight _ de TiAl(){ return Sight _ de TiAl；}
受保護:
字符串sname//景點名稱
string sight _ detial//景點說明
};
結構SI
{
字符串sname//景點名稱
int索引；//景點代碼
};
SI SightInfo[SIGHTS]；
地圖& ltint，string & gt結果；//距離和路徑的映射結構可以動態擴展。
向量& ltSight & gt景點；//VECTOR vector保存景點信息，目前的功能只是保存。
//但其強大的功能完全可以應對未來的功能擴展。
int MinDistanct = 50000//假設最小距離是壹個很大的值。
String Sight_Names = "林峰園蛟橋園青山園麥麓園"；//目標字符串
字符串Best _ Path//保存最佳路徑的字符串STRING。
Int DISTANCE[4][4] = {//查找表，用於存儲觸點之間的距離信息。
0, 1500, 2500, 2400,
1500, 0, 800, 0,
2500, 800, 0, 200,
2400, 0, 200, 0
};
Bool connect[4][4] = {//查找表，用於存儲聯系人之間的通信信息。
0, 1, 1, 1,
1, 0, 1, 0,
1, 1, 0, 1,
1, 0, 1, 0
};
void InitSights()
{//初始化景點的各種信息。
視覺信息[0]。索引= 0；
視覺信息[0]。sname = "麥路花園"；
視覺信息[1]。index = 1；
視覺信息[1]。sname = "袁鳳林"；
視覺信息[2]。指數= 2；
視覺信息[2]。sname = "蛟橋花園"；
視覺信息[3]。指數= 3；
視覺信息[3]。sname = "青山花園"；
瞄準鏡s1("林峰花園"，
“袁鳳林是江西財經大學唯壹壹所以計算機系理工科學生為主的計算機學院”)；
sights . push _ back(s 1)；
視線s2(“蛟橋花園”)，
“蛟橋花園是總部所在地江西財經大學以會計、貿易等金融教學為主的教學樓群”)；
sights . push _ back(S2)；
Sight3("青山花園"，
“青山園是江西財經大學主要教會計、貿易等金融的學生宿舍群”)；
sights . push _ back(S3)；
Sight4(“麥路花園”，
“麥鹿苑是江西財經大學外語、藝術等人文學科的學習園地”)；
sights . push _ back(S4)；
}
void Find_Ways(字符串開始，字符串結束，整數DIST，字符串路徑，整數深度)
{//遞歸調用，逐層查找連接的路徑，用此路徑繼續重復循環搜索。根據分析，妳可以
//已知所有最優解即最短路徑經過的接點數必須小於n，采用廣度優先遍歷。
//將count設置為循環深度，當count大於SIGHTS時退出循環。
int count = 1；
int i，j；
int start1 = 0，end 1 = 0；
int distanct = 0，store dist = 0；
字符串溫度、目標、路徑、存儲路徑；//臨時存儲，用於恢復遞歸調用。
//後來改了數據亂用。
計數+=深度；
if(count & gt；景點)
返回；
distant+= DIST；//距離累積
If(path=="") //第壹次，路徑初始化為第壹個聯系人姓名。
{
途徑=開始；
pathway += "= >；
}
如果(路徑！="")
pathway =路徑；
storeDist = distanct//填寫臨時存儲值
storePath = pathway
for(I = 0；我& lt景點；++i) //通過遍歷，找到景點名稱對應的數字。
{
if(start == SightInfo[i]。sname)
start1 = SightInfo[i]。指數；
if(end == SightInfo[i]。sname)
end1 = SightInfo[i]。指數；
}
for(I = 0；我& lt景點；I++) //算法核心步驟
{
if(連接[start1][i]！= 0)
{
If(i==end1) //如果找到路徑，保存它。
{
distant+= DISTANCE[start 1][end 1]；
for(j = 0；j & lt景點；++j)
{
if(end1==SightInfo[j].索引)
target = SightInfo[j]。sname
}
途徑+=目標；
results . insert(make _ pair(distant，pathway))；//保存結果路徑信息
distanct = storeDist//恢復數據供下次使用。
pathway = storePath
}
Else //分支路徑
{
for(j = 0；j & lt景點；++j)
{
if(i==SightInfo[j]。索引)
temp = SightInfo[j]。sname
}
path+= temp；
pathway += "= >；
distant+= DISTANCE[start 1][I]；
Find_Ways(臨時、結束、距離、路徑、計數)；//通過這個連接的分支
//繼續遞歸調用路徑，查找子層路徑信息。
distanct = storeDist//恢復數據
pathway = storePath
}
}
}
}
void Find_Best_Way()
{//這個函數是在上述函數執行後建立的，通過比較map映射結構中每條路徑的長度，可以
//選擇最佳解決方案
地圖& ltint，string & gt*叠代器itor = results . begin()；
while(itor！=results.end()) //求最小值
{
//cout & lt；& lt" distanct = " & lt& ltitor->；first & lt& ltendl
if(itor-& gt；first & ltMinDistanct)
mindistant = itor-& gt；第壹；
itor++；
}
itor = results . begin()；
while(itor！=results.end()) //查找最小值對應的整個路徑字符串。
{
if(itor-& gt；first = = MinDistanct)
best _ Path = itor-& gt；第二；
itor++；
}
}
int main(int argc，char *argv[])
{
int選擇；
size_t t1=0，T2 = 0；
字符串源，終止；
init sights()；
做{
cout & lt& lt"/////////////////////////////////////////////
& lt& lt* * * *請輸入您需要的服務號碼:* * * * * * * \ n
& lt& lt"**** 1.林峰花園介紹* * * * * * * \ n "
& lt& lt"**** 2.蛟橋花園介紹* * * * * * * \ n "
& lt& lt"**** 3.青山公園介紹* * * * * * * \ n "
& lt& lt"**** 4.麥鹿苑介紹* * * * * * * \ n "
& lt& lt"**** 5.查詢映射路徑* * * * * * * \ n "
& lt& lt"**** 6.退出查詢系統* * * * * * \ n "
& lt& lt"/////////////////////////////////////////////
& lt& ltendl
CIN & gt；& gt選擇；
開關(選擇)
{
案例1:
cout & lt& lt景點[0]。sight _ Name()& lt；& lt恩德爾
& lt& lt景點[0]。sight _ detial()& lt；& ltendl
打破；
案例二:
cout & lt& lt景點[1]。sight _ Name()& lt；& lt恩德爾
& lt& lt景點[1]。sight _ detial()& lt；& ltendl
打破；
案例三:
cout & lt& lt景點[2]。sight _ Name()& lt；& lt恩德爾
& lt& lt景點[2]。sight _ detial()& lt；& ltendl
打破；
案例4:
cout & lt& lt景點[3]。sight _ Name()& lt；& lt恩德爾
& lt& lt景點[3]。sight _ detial()& lt；& ltendl
打破；
案例5:
flag1:
cout & lt& lt"請輸入路徑的起點"
CIN & gt；& gt來源；
cout & lt& lt"請輸入路徑的結尾"
CIN & gt；& gt終止；
if((t 1 = Sight _ names . find(source，t 1))= = string::NPOs | |(T2 = Sight _ names . find(termination，t2))==string::npos)
{//檢查輸入數據是否包含非法字符。
cerr & lt& lt輸入的路徑節點不存在，請重新輸入
goto flag 1；
}
Find_Ways(source，termination，0，“”，0)；//找到所有可能的解決方案
Find_Best_Way()。//在所有可能的解中尋找最優解。
cout & lt& lt"最佳路徑是:"
& lt& lt"最小距離是(米):"
t 1 = 0；//恢復字符串下標以支持下壹個查詢。
T2 = 0；
打破；
案例6:
打破；
默認值:
cerr & lt& lt您的選擇超出範圍，請重新輸入:“< & ltendl
打破；
}
}while(選擇！=6);
系統(“暫停”)；
返回0；
}