山大公交线路上优化路径查询实验报告

1、山东大学 计算机科学与技术学院数据结构课程实验报告学号：姓名：班级:实验题目：公交线路上优化路径的查询实验学时：32实验日期： 一硬件环境： 软件环境: 实验内容与设计：1 .实验内容： 问题描述：最短路径问题是图论中的一个经典问题，其中的 Dijkstra算法一直被认为是图论中的好 算法，但有的时候需要适当的调整Dijkstra算法才能完成多种不同的优化路径的查询。对于某城市的公交线路，乘坐公交的顾客希望在这样的线路上实现各种优化路径的查 询。设该城市的公交线路的输入格式为：线路编号：起始站名（该站坐标）；经过的站点1名（该站坐标）；经过的站点2名（该站坐 标）； ；经过的站点n名（该站坐标

2、）；终点站名（该站坐标）。该线路的乘坐价钱。该线路 平均经过多少时间来一辆。车速。例如：63: A（32,45） ; B（76,45） ; C（76,90）;；N（100,100）。1 元。5分钟。1/每分假定线路的乘坐价钱与乘坐站数无关，假定不考虑公交线路在路上的交通堵塞。对这样的公交线路，需要在其上进行的优化路径查询包括：任何两个站点之间最便宜的 路径；任何两个站点之间最省时间的路径等等。基本要求：根据上述公交线路的输入格式，定义并建立合适的图模型。针对上述公交线路，能查询获得任何两个站点之间最便宜的路径，即输入站名S, T后，可以输出从SiIJT的最便宜的路径，/&出格式为：线路

3、x:站名S,，站名M1;换乘线路 x:站名M1,，站名M2；换乘线路x:站名MK，站名T。共花费x元。针对上述公交线路，能查询获得任何两个站点之间最省时间的路径（不考虑在中间 站等下一辆线路的等待时间），即输入站名 S, T后，可以输出从S到T的考虑在中间站等下一 辆线路的等待时间的最省时间的路径，输出格式为：线路 x:站名S,，站名M1;换乘线路 x:站名M1,，站名M2；换乘线路x:站名MK，站名T。共花费x时间。 针对上述公交线路，能查询获得任何两个站点之间最省时间的路径（要考虑在中间 站等下一辆线路的等待时间），即输入站名 S, T后，可以输出从S到T的考虑在中间站等下一 辆线路的等待

4、时间的最省时间的路径，输出格式为：线路 x:站名S,，站名M1;换乘线路 x:站名M1,，站名M2；换乘线路x:站名MK，站名T。共花费x时间。 实现提示：需深入考虑，应根据不同的应用目标，即不同的优化查询来建立合适的图模型。2 .实验设计：（1）实验需求：（1）输入数据：总的路线数目，各路线的站点数目，各站点的名称、位置坐标以及各(2)输出数据：输入数据的预处理结果(中间链表)与多个索引数组，三个不同权值 的邻接矩阵的值(距离，时间，票价)，以及各种不同需求下公交线路的结果。(3)功能：实现在不同查询条件下最优公交线路的输出。(2)实现思想：首先需要对输入的数据进行预处理。此处运用双向链表来

5、存储各站点的名称、横纵坐标及相对位置关系。然后用一个公交车 Bus类来存储各个线路的票价、速度及总线路。之后需要整合所有链表以生成邻接矩阵。首先将所有链表进行第一步处理，算出相邻两 点间距离存入第一个结点中原横坐标的位置，特别的，每个链表最后一个站点对应结点的相同位置则存储为 NoEdge (99999)。接着将各站点按顺序编号存于原链表纵坐标位置。接下 来将各路线的链表连接在一起形成一个存有全部路线的新链表wholeRoad。对wholeRoad进行处理。因为各路线中站点可能出现重复的情况，因此需要对编号进行 去重操作。遍历链表若发现某站点名出现过两次或两次以上，则将第二个以后的编号皆赋成第

6、一个的编号值，同时设置一个变量count来记录多次出现的的站点数。count初始值为0, 若出现一次重复则count加1,同时后面所有的编号赋为原编号减去 count。通过以上方法 来解决重复站点问题。根据最终站点编号建立原始编号与最终编号的索引数组和最终编号与站点名的索引数 组，并提供逆向查找方法。最后生成以距离为邻接矩阵时依照的就是最终的编号。不过在生 成过程中还是按照总线路链表进行循环，遍历总路线链表并根据索引将对应的距离存入真正 的位置，其他位置均设为 NoEdge而生成以时间为权值和以票价为权值的邻接矩阵过程基 本一样，只不过是将对应位置的值除相应速度或换为相应票价乘上线路编号的平方

7、(原因下方解释)。在最终邻接矩阵处理中主要运用 Dijkstra 算法。在时间最少与距离最短查询时直接使 用Dijkstra 算法即可。然而在票价最少时需要对算法进行调整。因为坐公交车时在一条线 路上一直乘坐只需要交一次车票钱因此不能直接将票价进行累加，然而不同线路间也可能存在票价相同的情况，因此也不能直接运用只要和上一条路线票价相同就不进行累加的方法。 为了避免不同线路票价权值相同，在赋值前先进行预处理，将票价改为相应票价乘上线路编 号的平方，并建立索引以及添加一个寻找原票价的方法。因此对于最少花费查询，只需在 Dijkstra 算法中加上寻找原票价的方法以及判断将要添加的路径的权值是否与上

8、一条相同 的步骤。最终结果是将存的点按索引转化为对应的站点名后按顺序输出，并将最小加权一并输 出。先进行判断如果加权和仍为NoEdge则输出“无路径！ ”。边从属的路线的判断首先通过每个路线的链表将所有可能的路线按顺序存储起来，然后通过查找方法找到对应的路线 名称即可。(3)使用说明：路线数，各站点坐标均为数字。查询方法选择时有效输入为1, 2, 3。其他输入会输出特定字符并结束程序。”是否继续时”只有输入y或Y才会继续。调试说明：输入三条线路进行测试。距离、时间问题不大，主要通过设置第一个线路票价为3而第二、三条线路票价均为1且经过组合它们均可到达同一个地方（d）来测试最少花费的正确 性。大

9、致线路图：调试程序：D;5tudyprc g ramCraiyT rainbi nDebugCrazyT ra in.e>e一 X请输入线路的个数;3请输入第1条路线的站点的个数，3输入各个站点的名称及坐标;a 1 1b 3 4e 5 2d 4 6清输入第1条路线线路的速度,票价!4 3请榆入第2条路线的站点的个数.请输入各个站点的名称及坐标：a 1 1e 7 4f S 3请输入第2条路线线路的速度,票价:5 1请输入第3条路线的站点的个数,4请输入各个站点的名称及坐标1g 2 2e7411 3 3d 4 6请输入第3条路线线路的速度,票价：3 1a(3. 6, l)->b(2.

10、82, 2)->c(4. 12,3)->d(99999, 4)a(6.7,5)->e (1.41, 6)->f (99999, 7)g(5.38, 8)->e(l. 41, 9)->h(5,10)->d(99999,11)a(3.6,1)->b(2.82, 2)->c(4. 12,3)->d(99999? 4)->a(6.7,5)->e(l. 41, 6)-f (9999% 7)->g(5 .38,8)->e(l. 41, 9) ->h(5, 10)->d(999,11)a(3.6, l)->

11、b(2.82, 2)->c(4. 12,3)->d(99999, 4)->a(6, 7, l)->eCl. 41,5)->f(99999, 6)->g(5 .38,7)->e(l. 41, 5)->h(5, 8)->d(99999,4)1 2 3 4 1 5 6 7 5 8 4abcdefgh3 1 13 4 912 21 23 32 34 43 15 51 56 65 75 57 58 85 84 4899999. 003.6099999.0099999.006. 7099999. 0099999. 0099999. 003. 60999

12、99. 002. 8299999. 0099999.0099999. 0099999.0099999. 0099999. 002. 8299999. 004. 1299999.0099999. 0099999.0099999. 0099999.0099999. 004. 1299999. 0099999.0099999. 0099999.005. 006.7099999. 0099999. 0099999. 0099999. 001. 415.381. 4199999.0099999. 0099999. 0099999. 001.4199999. 0099999.0099999. 009999

13、9.0099999. 0099999. 0099999. 005.3899999. 0099999.0099999. 0099999.0099999. 0099999.005. 001.4199999. 0099999.0099999. 0099999.000. 9099999. 0099999. 001.3499999. 0099999.0099999. 000. 9099999. 000. 7099999. 0099999.0099999. 0099999.0099999. 0099999.000. 7099999. 001. 0399999.0099999. 0099999.009999

14、9. 0099999.0099999. 001. 0399999. 0099999. 0099999. 0099999.001. 661.3499999. 0099999. 0099999. 0099999.000. 281.790. 4699999.0099999.0099999.003.0099999.0099999.004. 0099999.0099999. 0099999.00ggggg. oo99999. 003.0099999. 003.0099999. 0099999. 0099999. 0099999. 0099999. 0099999. 0099999. 0099999. 0

15、03. 0099999.003.0099999. 0099999.0099999. 0099999. 00999gg. 001.6699999. 00ggggg. oo3.0099999. 0099999. 0099999. 0099999. 009.001. 790. 464. 0099999. 0099999. 0099999. 0099999. 004. 009. 009. 0099999.0099999.0099999.0099999.0099999.0099999.004. 0099999.0099999.0099999.00999gg. 0099999. 0099999. 0099

16、999. 0099999. 0099999. 009. 0099999. 0099999. 0099999. 0099999.0099999.0099999.0099999.0099999.009.009. 0099999.0099999.0099999.00请选择您想选择的查询方法：L最迪路径2 .最小花费3 .最短时间1请输入想查询的起始站与终点站：g bg站到b站的最处路径长度：68g就蓟b患的最短蓝径为: g -> （公交线路3）e -> （公交线路2）a（公交线路l）b是否继续?<Y/N> 请选择您想选择的查询方法；1 .最短路径2 .最小花费3 .最短时间n

17、 乙 请输入想查询的起始站与终点站；a da站到d站的最少花费：2a站到d站的最省钱路径为：a -> （公交线路2） e -> （公交线路3）h -> （公交线路3）d 是否继续99清选择您想选择的查询方法：1 .最短电径2 .最小花费3 .最短时间工输入想查询的起始站与终点站：e站到e站的最短时间：2.94c站到e站的最省时路径为：c -> （公交线路Db -> （公交线路4 （公交线路2储 是否维续?<"N>解选择您想选择的查询方法，L最短路径2 ,最“讹费3.最短时间5心口口 wst be kidding me! !0T2_Proces

18、s returripd 0 （0x0）executi an tiine : 671.064 £Press any key to continue.(5)实验代码：头文件 SickRoad.h#include<iostream>#include<string>#include<cmath>#include<cstdio>using namespace std;#define NoEdge 99999/无路线int number;/公交线路数int count=0;/多次出现的地点数int *area;double *price;车票价格数

19、组int *speed;/车速数组double *DistanceMap;/以距离为权值的邻接矩阵double *PriceMap;/以票价为权值的邻接矩阵double *TimeMap;/以时间为权值的邻接矩阵int *numIndex;/车站编号索引string *nameIndex;/ 车站姓名索引int *priceIndex;/ 票价索引int *lpriceIndex;/处理后的票价int range;/总车站数double Restrict(double a)/double 保留两位小数方法 double tem=int(a*100);return tem/100;double

20、getDistance(double a,double b,double c,double d)/求两点间距离方法 return Restrict(sqrt(a-c)*(a-c)+(b-d)*(b-d);class RChainNode/1表结点类friend class BusRoutine;friend class RChain;public:string station;double px;double py;RChainNode *next;RChainNode *prior;class RChain/糖表类friend class BusRoutine;public:RChain()

21、first = 0;RChain();bool IsEmpty() return first = 0;int Length() const;RChainNode *getFirst()得到链表头结点 return first;RChain &Insert(const string &s, const double &x,const double &y);RChain &IInsert(RChainNode *rn);void Output(ostream &out) const;string getStation() 返回站点名return fi

22、rst->station;RChain &Rearrange(double &y);RChain &reCharge(RChain &r);RChain &dRejudge();private:RChainNode *first;；RChain:RChain()RChainNode *next;while (first)next = first->next;delete first;first = next;int RChain二Length() constRChainNode *current = first;int len = 0;whi

23、le (current)len+;current = current->next;return len;RChain &RChain二Insert(const string &s, const double &x, const double &y)从后插入新结点 if (!first)first = new RChainNode;first->station = s;first->px = x;first->py = y;first->next = 0;first->prior = 0;_else RChainNode *p

24、= first; while (p->next) p = p->next;RChainNode *r = new RChainNode; r->station=s;r->px = x; r->py = y; p->next = r; r->prior = p; r->next=0; return *this;RChain &RChain:IInsert(RChainNode *rn)以后插入一个已有结点 if(first) RChainNode *tem=rn;RChainNode *p = first; while (p->nex

25、t) p = p->next;p->next=tem; tem->prior=p; else first=rn;RChain &RChain二Rearrange(double &y)/1车站链表处理，得到距离及对应累加序号 RChainNode *Current=first;for(Current; Current->next; Current=Current->next) RChainNode *tem=Current->next;Current->px=getDistance(Current->px,Current->p

26、y,tem->px,tem->py);Current->py=y;y+;Current->px=NoEdge;Current->py=y;y+;RChain &RChain:reCharge(RChain &r潮两个链表连接在一起 this->IInsert(r.getFirst();if(!first)this->first=r.getFirst(); return *this;RChain &RChain二dRejudge()对链表去重，重新编号range=Length();RChainNode *current=first

27、;for(int i=0; i<Length(); i+)if(i=0)current->py+=0;current=current->next;else RChainNode *temp=first; int flag=0;for(int j=0; j<i; j+) if(current->station=temp->station) 查找是否有重复站点 current->py=temp->py; flag+;count+;/记录重复站点个数 break; temp=temp->next;if(!flag) current->py-

28、=count;current=current->next;return *this; void RChain二Output(ostream &out) const/重载，输出链表RChainNode *current;for (current = first; current->next; current = current->next)out << current->station << '('<<current->px<<','<<current->py&

29、lt;<')'<<"->"out << current->station << '(' << current->px << ',' << current->py << ')' << endl; ostream &operator<<(ostream &out, const RChain &x)x.Output(out);return out; clas

30、s BusRoutine/公交车类public:BusRoutine()Num=0;Speed=0;Stage.first=0;void SetStage(int nm,int n)/设置几路及站点数Name=nm;Num=n;string s;double x, y;cout << "请输入各个站点的名称及坐标："<< endl;for (int j = 0; j < n; j+)cin >> s >> x >> y;Stage.Insert(s, x, y);void setOthers(int s,in

31、t p)/ 设置速度及票价Speed=s;Price=p;RChain &getStage()return Stage;void aOutPut()打印全部信息cout<<"线路"<<Name<<endl;cout << Stage;cout<<"Speed: "<<Speed<<"km/h"<<endl;cout<<"Price: "<<Price<<"RMB&qu

32、ot;<<endl;void bOutPut()仅打印公交线路cout << Stage;int getPrice()/ 获得票价return Price;int getSpeed()/获得速度return Speed;int getNum() return Num;int getName() return Name;private:int Name;/公交线路编号int Num;int Speed;int Price;RChain Stage;BusRoutine *Bus;/公交车数组RChain wholeRoad;/SE合后的总路线链表void Change(B

33、usRoutine *Bus,int n)/对每条公交路线进行重排，求距离并编号 double x=1;for(int i=0; i<n; i+)(Busi.getStage().Rearrange(x);void getNumIndex()/得到各站点序号的索引Iint all=wholeRoad.Length();numIndex=new intall+1;numIndex0=0;RChainNode *temp=wholeRoad.getFirst();for(int i=1; i<=all; i+)numIndexi=temp->py;if(i!=all) temp=

34、temp->next;void numIndexOutPut()for(int i=1; i<=range; i+) cout<<numIndexi<<""cout<<endl<<endl;void getNameIndex()/各站点序号与名字的对应关系range-=count;nameIndex=new stringrange+1;RChainNode *temp=wholeRoad.getFirst();nameIndex0=""for(int i=1; i<=wholeRoad.L

35、ength(); i+)nameIndexnumIndexi=temp->station;if(i!=wholeRoad.Length() temp=temp->next;void nameIndexOutPut()for(int i=1; i<=range; i+) cout<<nameIndexi<<""cout<<endl<<endl;bool searchNo(string a,int &b)/根据站点名得到其编号for(int i=1; i<=range; i+)if(a=nameIn

36、dexi)b=i;return true;return false;void getPriceIndex()得至 ij 价格索弓 IpriceIndex=new intnumber+1;priceIndex0=0;for(int i=1; i<=number; i+)priceIndexi=Busi-1.getPrice();void getlPriceIndex()/得到处理后价格lpriceIndex=new intnumber+1;lpriceIndex0=0;for(int i=1; i<=number; i+)lpriceIndexi=priceIndexi*i*i;vo

37、id priceIndexOutPut()for(int i=1; i<=number; i+) cout<<priceIndexi<<""cout<<endl<<endl;void lpriceIndexOutPut()for(int i=1; i<=number; i+) cout<<lpriceIndexi<<"" cout<<endl<<endl;int searchPrice(int p)/根据处理后价格查找原价格for(int i=1;

38、 i<=number; i+)if(p=lpriceIndexi)int temp=priceIndexi;return temp;return NoEdge;void getArea()/依此得到各站点中可能出现的边 int bound=2*(wholeRoad.Length()-number)+1; area=new intbound;int i=1,ii=1;int sign=0;while(i<=bound-1)for(int j=0; j<number; j+)for(int k=1; k<Busj.getNum(); k+)areai=10*numIndex

39、ii+sign+numIndexii+1+sign;areai+1=10*numIndexii+sign+1+numIndexii+sign;i=i+2;ii+;if(k=Busj.getNum()-1)sign+;void areaOutPut()int bound=2*(wholeRoad.Length()-number)+1; for(int i=1; i<bound; i+)cout<<areai<<""cout<<endl<<endl;int areaCheck(int a,int b)/根据两点判断其从属的路

40、线名 int bound=2*(wholeRoad.Length()-number)+1;int temp=10*a+b;int i=1;for(i; i<bound; i+)if(areai=temp)break;int roadNumbernumber+1;roadNumber0=0;for(int j=1; j<=number; j+)roadNumberj=Busj-1.getNum()+roadNumberj-1;for(int j=0; j<number; j+)if(i>2*(roadNumberj-j)&&i<=2*(roadNum

41、berj+1-j-1)return j+1;void getDistanceMap()/得到以距离为权值的邻接矩阵DistanceMap=new double *range+1;for(int i=0; i<=range; i+)DistanceMapi=new doublerange+1;RChainNode *tem=wholeRoad.getFirst();for(int i=0; i<=range; i+)for(int j=0; j<=range; j+)DistanceMapij=NoEdge;for(int i=1; i<=wholeRoad.Length

42、()-1; i+)DistanceMapnumIndexinumIndexi+1=tem->px;DistanceMapnumIndexi+1numIndexi=tem->px; tem=tem->next;void dMapOutPut()打印出以距离为权值的令口接矩阵for(int i=1; i<=range; i+)for(int j=1; j<=range; j+)printf(" %8.2f ”,DistanceMapij);cout<<endl;cout<<endl;void getTimeMap()/得到以时间为权值

43、的邻接矩阵TimeMap=new double *range+1;for(int i=0; i<=range; i+)TimeMapi=new doublerange+1;for(int i=0; i<=range; i+)for(int j=0; j<=range; j+)TimeMapij=DistanceMapij;int i=1;while(i<wholeRoad.Length()for(int j=0; j<number; j+)for(int k=0; k<Busj.getNum(); k+)if(k!=Busj.getNum()-1)TimeM

44、apnumIndexinumIndexi+1=Restrict(TimeMapnumIndexinumIndexi+1/Busj.g etSpeed();TimeMapnumIndexi+1numIndexi=TimeMapnumIndexinumIndexi+1;i+；if(k=Busj.getNum()-1) i+；void tMapOutPut()打印出以时间为权值的邻接矩阵for(int i=1; i<=range; i+)for(int j=1; j<=range; j+)printf(" %8.2f ”,TimeMapij);cout<<endl;

45、 cout<<endl;void getPriceMap()/得到以时间为权值的邻接矩阵PriceMap=new double *range+1;for(int i=0; i<=range; i+)PriceMapi=new doublerange+1;for(int i=0; i<=range; i+)for(int j=0; j<=range; j+) PriceMapij=DistanceMapij;int i=1;while(i<wholeRoad.Length()_for(int j=0; j<number; j+) for(int k=0;

46、 k<Busj.getNum(); k+)if(k!=Busj.getNum()-1) PriceMapnumIndexinumIndexi+1=Busj.getPrice()*Busj.getName()*Busj.getName();PriceMapnumIndexi+1numIndexi=PriceMapnumIndexinumIndexi+1;i+；if(k=Busj.getNum()-1) i+；void pMapOutPut()打印出以票价为权值的令口接矩阵for(int i=1; i<=range; i+)for(int j=1; j<=range; j+)pr

47、intf(" %8.2f ”,PriceMapij);cout<<endl;cout<<endl;/Dijkstra 算法/各数组都从下标1开始double *dist; /表示当前点到源点的最短路径长度int *prev; /记录当前点的前一个结点int line=2*(range-1);/图的结点数和路径数/ range - n nodes/ v - the source node/ dist - the distance from the ith node to the source node/ prev - the previous node of t

48、he ith node/ c - every two nodes' distancevoid initialize。dist=new doublerange+1;prev=new intrange+1;for(int i=1; i<=range; +i)disti = NoEdge;void Dijkstra(int n, int v, double *dist, int *prev, double *c)bool srange+1; /判断是否已存入该点到 S集合中for(int i=1; i<=n; +i) disti = cvi;si = 0;/初始都未用过该点if(

49、disti = NoEdge)previ = 0; elseprevi = v;distv = 0;sv = 1;/依次将未放入S集合的结点中，取dist口最小值的结点，放入结合S中/ 一旦S包含了所有V中顶点，dist就记录了从源点到所有其他顶点之间的最短路径长 度/注意是从第二个节点开始，第一个为源点for(int i=2; i<=n; +i)int tmp = NoEdge;int u = v;/找出当前未使用的点j的distj最小值for(int j=1; j<=n; +j)if(!sj) && distj<tmp) u = j;/ u保存当前邻接点中

50、距离最小的点的号码tmp = distj;su = 1;/表示u点已存入S集合中/更新distfor(int j=1; j<=n; +j)if(!sj) && cuj<NoEdge) double newdist = distu + cuj;if(newdist < distj) distj = newdist;prevj = u;/查找从源点v到终点u的路径，并输出void ReDijkstra(int n, int v, double *dist, int *prev, double *c) bool srange+1; /判断是否已存入该点到 S集合中f

51、or(int i=1; i<=n; +i)disti = searchPrice(static_cast<int>(cvi);si = 0;/初始都未用过该点if(disti = NoEdge)previ = 0;elseprevi = v;distv = 0;sv = 1;/依次将未放入S集合的结点中，取dist口最小值的结点，放入结合S中/ 一旦S包含了所有V中顶点，dist就记录了从源点到所有其他顶点之间的最短路径长 度/注意是从第二个节点开始，第一个为源点for(int i=2; i<=n; +i)int tmp = NoEdge;int u = v;/找出当前

52、未使用的点j的distj最小值for(int j=1; j<=n; +j)if(!sj) && distj<tmp)u = j;/ u保存当前邻接点中距离最小的点的号码tmp = distj;su = 1;/表示u点已存入S集合中/更新distfor(int j=1; j<=n; +j)if(!sj) && cuj<NoEdge)double newdist;if(cuprevu!=cuj)/是否与上一边的权值相同newdist = distu + searchPrice(cuj);/不同贝 U 力口上真正的权值 elsenewdist

53、= distu;/相同则保持原值if(newdist < distj) distj = newdist; prevj = u;/查找从源点v到终点u的路径，并输出void searchPath(int *prev,int v, int u)int querange+1;int tot = 1;quetot = u;tot+;int tmp = prevu;while(tmp != v)quetot = tmp;tot+;tmp = prevtmp;quetot = v;for(int i=tot; i>=1; -i)if(i != 1)cout << nameIndex

54、quei << "-> "cout<<"(公交线路"<<areaCheck(quei,quei-1)<<")" elsecout << nameIndexquei << endl;/完毕0-0void getDRoad(string s,string e)int startp,endp;/各数组都从下标1开始/输入结点数if(searchNo(s,startp)&&searchNo(e,endp)initialize。;Dijkstra(ra

55、nge, startp, dist, prev, DistanceMap);/最短路径长度if(distendp=NoEdge)cout<<"不可达！ ！ ！ "<<endl;elsecout << s<<"站至U "<<e<<”站的最短路径长度："<< distendp << endl;/路径cout << s<<"站至U "<<e<<”站的最短路径为：" searchP

56、ath(prev, startp, endp);elsecout<<"No Such Station! ! "<<endl;void getTRoad(string s,string e)int startp,endp;/各数组都从下标1开始/输入结点数if(searchNo(s,startp)&&searchNo(e,endp)initialize。;Dijkstra(range, startp, dist, prev, TimeMap);/最短路径长度cout << s<<"站至U "&

57、lt;<e<<"站的最短时间："<< distendp << endl;/路径cout << s<<"站至I "<<e<<"站的最省时路径为：" searchPath(prev, startp, endp);elsecout<<"No Such Station! ! "<<endl;void getPRoad(string s,string e)int startp,endp;/各数组都从下标1开始/输入结点数if(searchNo(s,startp)&&searchNo(e,endp)initialize。;ReDijkstra(range, startp, dist, prev, PriceMap);/最短路径长度cout << s<<"站至U "<<e<<”站的最少