最佳公交线路乘车方案

最佳线路乘车方(T矩阵)和最小换乘矩阵(Q矩阵)，得到求解最少换乘次数。然后依次考虑总时间与总费用最少，即在公汽网络中利用改进的Dijkstra算法，以Q矩阵限制T标号S3359

S1828（最少费用：3元；最少耗时：101钟，其他详见表（一标，耗时为第二目标、费用为第三目标的数学模型二，利用改进的Dijkstra算法求出问题1的6S3359

线路)出行,线路交通阻抗值是指乘客在线出行的出行时间、费用、方便性(如换乘)等综合费用指标，由此改进得到模型四。改进的思路是将乘公汽Dijkstra算法求出问题1的6对起始站→终到站之间的最佳路线：如SS1828（最少费用：3元，最少耗时分钟，其他的详见表（四）～表（七：换乘交通阻抗Dijkstra1、问题的简述与分问题重述我国人民翘首企盼的第29届奥运会明年8月将在举行，届时有大量观众到现场奥运比赛其中大部分人将会乘坐公共交通工（简称包括公汽、地铁等）出行。这些年来，城市的系统有了很大发展，市的线路已达800条以上使得公众的出行更加通畅便利但同时也多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决线路选择问题的自主查询计算机为了设计这样一个系统，其是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。请解决如下问题： (4)、 (5)、 2问题分地铁线为线路（地铁站的加入有使得该地铁站附近的站变连通等特性），达终点。换乘问题的实质就是给出起始点、目标点后，给用户提供乘车方案。通过对乘客的出行心理研究，其结果表明，“换乘次数”是大部分公时与换乘的次数、等车的时间、车沿途停靠站点耗时以及距离的长短密切相关。因此，对于出行耗时和距离长短，可转化为换乘次数最少的基础上车沿途行驶距离长短和停靠站点多寡的问题。讨论的换乘算法就是以“换乘次数最标，来寻求出行的最佳路径。乘客出行和汽车运货所考虑的因素是不同的，汽车运货关心的是如何选择最近距离，最大程度的省时省油；而乘客出行考虑的是出门的方便性和舒适性，所以道路网络中的最短路径和线路的最短路径的意义是不同的。道路网络中的最短路径只要找出两点之间路径距离为最短即可。但是在网有一段的步行距离的代价，而且在站台等车也是要消费时间的。所以对 乘法的思想描述如下：根据人们的出行习惯，在选择从SB先会先看经过AB没有直达车.就会考虑换一次车的方案：即判断经过A站的车与经过B站的车是否有公共站点C，如果有，则可以在公共站点C处转车；如果没有换一次车的方案，则又要考虑乘坐经过A点的车到某一站c下车，判断经过c站点的车与经过B站点的车是否有公共站点D，如果有就再到DB；如果没有，则需念，用以描述站点空间位置上的距离关系。通常是根据人们的行为习惯和平2、问题假设与符号说1：任意两个车站之间都可以通过公共汽车直达或换乘到达23s代表公汽站点号（s0001~3957mi代表第iTa代表地铁路线的编号（a12n代表地铁站点的编号（n01,02, ,393、模型的建立及求道路网用简单图G表示而结点集V(G)是所 站点的集合边集是所有道路边的集合，V(G)的基数为n，即︱V(G)︱=n，表示有n个不同的公︱边。车线li可定义为有序点集li={k,n1,n2,…,nvi︱nvi∈V(G)},vili上的站点数，k∈{0,1,2}}式(1)表示车线可从n1点出发依次经过n2，n3，…,nvi-1到达nvi点,如果是环线,如旅游环线,k=2；k=1；k=0车线形成车线网络X：X={li︱i=1,2,…,Nl,，Nl为网络中车线数}[2]，途经由站x到站y线路集合记为：Lx,y)li|li为由站x可达站yi条线路记ui0,i2...ik1为 网络中的k个换乘点，w(i,i0),(i1,i2),...(ik1,j)E(G)，而对网络中从站i到站j，选定具有k个换乘点i0,i2...ik1的一个乘车方案为：im0,i0,i0m1,i1,...,ikmk,j；k=0i0

短有关。定义从站x到站y搭乘车次为l的车的耗时为tl(x,y)，则从站i到站j按上述乘车换乘方案最小总耗时T(i,j)为：T(i,j)tm0(i,i)tm1(i,i)...tmk

, 0

k其中tmv(x,y)为第v次换乘时，搭乘由站x可达站y所有有向tmv(x,y)

liL(x,y

定义从站x到站y搭乘车次为l的车的费用为fl(x,y)，则从站i到站j按上述乘车换乘方案所需最小费用F(i,j)为：F(i,j)fm0(i,i)fm1(i,i)...fmk

, 0

k其中fmv(x,y)为第v次换乘时，搭乘由站x可达站y所有有向fmv(x,y)min

liL(x,y

fli(x,minT(i,j)

mintm0(i,i)tm1(i,i)...tmk

,

0

kminF(i,j)

minfm0(i,i)fm1(i,i)...fmk

,

0

k

(i,i1),(i1,i2),...(ik1,j)E(G)；即由站i乘车经有限k次换乘可达站jtmv(x,y)

liL(x,y

fmv(x,y)

liL(x,y

fli(x,首先定义直达矩阵

T(TTiji→jnT i0 0

i图1为一网络.其中1～15为节点

R1～R5为线路,用实线段表示图图由定义得节点1～9的T011100100 001010011 000000000 000000100 000000111 000010100000000000 000000001000000000 001010111 000000112 000000000 000000000000000001 000000111 000000000 000000000 000000000 最少换乘矩阵(Q引入Q矩阵,Q(Q)， 为使得Tn

的n的最小值n∈[1 Qi,j1表示从节点i→j必要的最少换乘次数.图1网络的Q矩阵 式中∞表示2

=3表示从节点4到152次.利用Q矩阵可以确定最少换乘次数,还可用于评价网络.若计算所得很大,说明从节点i→j需多次换乘,方便性较差,可通过增加或改善i,j间线路来减小Qij.对于一条线的节点,应用T矩阵所得结果可能偏大,但这并不影响Q.当Tk为偏大值时,必存在pk使得Tpj≠0.如T2 113换乘点为2,此值偏大(1→3达而

=1,故

=DijkstraT[i]赋值为，oT[o]=0,P其他所有标号都为TT[v]=min(T[u]+G[u][v],T[v])在所有标号为TT[v]2PDijkstra1．初始化得到邻接表graph[i],每个元素包含graph[i].kgraph[i].f,graph[i].T读入所有的路线信息对于任意一条路线T设其经过的站点为s1,s2..sk，1<=ij<=kij，sisjk1,f=3,T（ji）*3k[i]=，k[o]=0,oP都为TPuV，如果存在v，并且(u,v)边所查找到的邻接表元素为link,那么mink[v]=min(mink[u]+link.k,mink[v])P标号P标号u找所有标号为Tmink[v]3Pf[i]=，f[o]=0,1Pu，Vv，link，那么minf[v]min(minf[u]+link.f,minf[v])|mink[v]=mink[u]+找所有Tf[v]7P10T[i]，T[o]=0,1P、TP的节点u，V，节点v，link，那么minT[v]=min(minT[u]+link.T,minT[v])|其中要求mink[v]=mink[u]+minf[v]=minf[u]+TminT[v]11Pmink[i],minf[i],minT[i]。（1（2于是得到（1）表（一S3359—3101S1557—3106S0971—3128S0008—283S0148—3106S0087—265（2）表（二）S3359—3101S1557—3106S0971—3128S0008—283S0148—3106S0087—2652xyzl的车的耗时为tl(xy 则从站i到站j按上述乘车换乘方案最小总耗时T(i,j)为T(i,j)tm0(i,i)tm1(i,i)...tmk

,

（z

0

k 其中tmv(xyvzxy ztmv(xyzv

liL(x,

z定义从站点x到站点yzlfl(xyzijF(i,jF(i,j)fm0(i,i)fm1(i,i)...fmk

,

0

kfmv(xy为第vzxy zfmv(xyzv

liL(x,

fli(x,minminT(i,j)

mintm0(i,i)tm1(i,i)...tmk

,

0

kminF(i,j)

minfm0(i,i)fm1(i,i)...fmk

,

0

k（其中ui0,i2...ik1 网络中的k个换乘点，w(i,i0),(i1,i2),...(ik1,j)st.(i,i1),(i1,i2),...(ik1,j)E(G)；即由站i乘车经有限k次换乘可达站jztmv(x,y)zi

liL(x,

zfmv(x,y)zv

liL(x,

fli(x,将地铁的信息换成与之等价的广义读入所有的地铁信息并转化成广义路线信息：若两站能通过地铁站步行到达则在这两个站之间生成一条广义线路；若两站能通过乘坐地铁到达则在这两个站之间生成一条广义线路。对于任意一条广义路线在sisjk1,f=3,T=(j–i)*2.5；若通过地铁站步行到达的边则k=0,f=123,T=5。将它们都补入问题1已经做好的利用问题中1的算法，求解出最佳乘车线路。（3表（三）S3359—3101S1557—S19193106S0971—L013，3128S0008—280S0148—L308 3103D20-S0087—135xy按第rl的车的耗时为tl(xy 则从站i到站j按上述乘车换乘方案最小总耗时T(i,j)为T(i,j)tm0(i,i)tm1(i,i)...tmk

,

（r

0

k 其中tmv(xyvrxy rtmv(xyrv

liL(x,

tli(x,z定义从站点x到站点y按第r种换乘方式搭乘车次为l的车的费用为fl(xy，因步行换乘方式的费用为0，则可引入0—1变量进行求解，于是从站点i到站点jF(i,j)zF(i,j)am0fm0(i,i)am1fm1(i,i)...amkfmk

,j)

0

k其中

fmv(xyvrxy rfmv(xyrv

liL(x,

fli(x,3minminT(i,j)

mintm0(i,i)tm1(i,i)...tmk

,

0

kminF(i,j)

minam0fm0(i,i)am1fm1(i,i)...amkfmk

,

0

k（其中ui0,i2...ik1 网络中的k个换乘点w(i,i0),(i1,i2),...(ik1,j)

在mi 步行在mi

(i,i1),(i1,i2),...(ik1,j)E(G)；即由站i乘车经有限k次换乘可达站jztmv(x,y)zi

liL(x,

zfmv(x,y)zv

liL(x,

fli(x,将任意两站点间的步行信息转化成两站点间 信息。在用问题1的程序T，设其经过的站点为si,sjsi和sj连一条k0,f=0,T=Tij，114JeJf转换成价值时间，n票价480法定年工作天数tp

式中n为换乘次数居民人均年收入为8000,法定工作5周由于重点讨论换乘影响为简化计算忽略步行时间、等车时间以及换乘时间,在计算交通阻抗时,仅考虑车行驶时间及票价,即tttetf，其中t代表从站点i到站点jtetf 铁的价值时间，1，2代表权重系数定义从站点i到站点j的价值时间tb（b可以为e或者f

bk，其中be,fi1i1mint

minuV(GwE(G

te

t2t（其中ui0,i2...ik1 网络中的k个换乘点w(i,i0),(i1,i2),...(ik1,j)

(i,i1),(i1,i2),...(ik1,j)E(G)；即由站i乘车经有限k次换乘可达站j对于模型四的求解，同样运用求解模型二的算法，具体实现见附录表（四）当1=0.001，2=0时的最佳路线3733106596555587.5钟无325表（五）当1=1,2=100000费S3359—S0073,6S1557—4S0971—D15—S2534,S22106S0008—L200,T1,T2,S2534—D15D12，D25—5S0148—L024,D15—S2534，S22106S0087—S0087—D27D36—3表（六）当1=2=1时的最佳路线5499钟5L259,T2,S3874—D30D25—5L024,5S0087—D27D36—325钟表（七）当1=0.001，2=1000时的最佳路线费S3359—6S1557—4S0971—S0567—D15—695钟S0008—L200,T1,T2,S2534—D155S0148—L024,S1487—D15—6S0087—S0087—D27D36—3从表（四）～表（七）可以知道，1，2可以根据个人的需要自己设置，这另外，对所有线路，为了评定各条线的乘车人口密度和交通拥挤程度还以考虑在各模型中引入一个舒适度因子li（li表示一个线路li的舒适度，若该值越5、模型该题采用了网络中改进的Dijkstra算法，搜索解的速度非常快。算法型推广中多目标转化为单目标函数，即将费用、耗时等因素转化为价值时间，在问题三中步行也看作乘车的情况，这样模型就可以在模型二的0，那么对于模型二中的费用的目标函数就需要进行改进这里我们引入了0—1变量在每个单独的费用前乘，参考文献[1]deDOrtuzarJ,WillumsenLG.Modellingtransport[M]England:JohnWiley&Sons [2],赵永昌,.公共交通网络路径算法[J].系程,1987,5(1):53-[3]等.公共交通系统最佳路径算法[J].东南大学学报,2004,34(2):265-[4],,网络换乘矩阵的分析与算法 系统工程第21卷第6期(总第120期)[5]朱,基于最小换乘次数的最优路径算法 附录#include<stdio.h>#include<string.h>constintMAXN constintMAXROUTE= constintinfinity struct{ p,len,cost,num; route[MAXROUTE+ bool N,source,target,voidaddEdge(intu,intv,intlen,intnum,int{Tgraph*x=newTgraph;x->p=v;x->len=x->num=if(len<=20)x->cost=1;if(len<=40)x->cost=2;elsex->cost=3;if(type==2)x->cost=1;x->next=graph[u];graph[u]=x;}voidinit{intfor(inti=0;i<MAXROUTE;{intnum,tot,scanf("%d%d%d",&num,&type,for(intj=0;j<tot;j++)scanf("%d",&List[j]);for(intj=0;j<tot;j++)for(intk=j+1;k<tot;addEdge(List[j],List[k],k-j,num,route[num][0]=for(intj=0;j<tot;j++)route[num][j+1]=}}voidMinimalSwap{for(inti=0;i<MAXN;i++)minswap[i]=infinity;memset(used,false,sizeof(used));minswap[source]=0;for(inti=0;i<MAXN;{intmin=infinity,for(intj=0;j<MAXN;if(!used[j]&&minswap[j]<{min=minswap[j];minp=}if(min==infinity)return;used[minp]=true;Tgraph*x=graph[minp];while(x!=NULL){if(minswap[minp]+1<minswap[x->minswap[x->p]=minswap[minp]+1;x=x->next;}}}voidMinimalCost{for(inti=0;i<MAXN;i++)mincost[i]=infinity;memset(used,false,sizeof(used));mincost[source]=0;for(inti=0;i<MAXN;{intmin=infinity,for(intj=0;j<MAXN;if(!used[j]&&mincost[j]<{min=mincost[j];minp=}if(min==infinity)return;used[minp]=true;Tgraph*x=graph[minp];while(x!=NULL){if(minswap[minp]+1==minswap[x->if(mincost[minp]+x->cost<mincost[x->p])mincost[x->p]=mincost[minp]+x->cost;x=x->}}}voidMinimalDist{for(inti=0;i<MAXN;i++)mindist[i]=infinity;memset(used,false,sizeof(used));mindist[source]=0;for(inti=0;i<MAXN;{intmin=infinity,for(intj=0;j<MAXN;if(!used[j]&&mindist[j]<{min=mindist[j];minp=}if(min==infinity)return;used[minp]=true;Tgraph*x=while(x!={if(minswap[minp]+1==minswap[x->if(mincost[minp]+x->cost==mincost[x->p])if(mindist[minp]+x->len<mindist[x->p]){mindist[x->p]=mindist[minp]+x->len;previous[x->p]=minp;preEdge[x->p]=}x=x->}}}voidfind(intu,intv,intnum,int{for(inti=1;i<route[num][0];if(route[num][i]==u&&route[num][i+len]=={for(intj=i;j<i+len;j++)printf("S%04d->",route[num][j]);printf("S%04d\n",route[num][i+len]);}}voidbacktrace(int{if(v==source)return;backtrace(previous[v]);printf("\nTime%d:TakeBusLine%03d\n",time,preEdge[v]->num);printf("Route :");find(previous[v],v,preEdge[v]->num,preEdge[v]->}int{printf("StartStation:");scanf("%d",&source);printf("TargetStation:");scanf("%d",&target);printf("\n");printffreopen("bus.txt","r",stdin);init();MinimalSwapMinimalCost();MinimalDist();//freopen("result.txt","w",printf ysisReportprintf(" MinimalSwapis%d\n",minswap[target]-1);printf(" MinimalCostis%d\n",mincost[target]);printf MinimalTimeis%d\n",mindist[target]*3+(minswap[target]-1)*time=0;backtrace(target);return}附录#include<stdio.h>#include<string.h>constintMAXN constintMAXROUTE= constintinfinity struct{ p,len,cost,num; route[MAXROUTE+ bool N,source,target,voidaddEdge(intu,intv,intlen,intnum,int{Tgraph*x=newTgraph;x->p=v;x->len=x->num=if(len<=20)x->cost=1;if(len<=40)x->cost=2;elsex->cost=3;if(type==2)x->cost=1;x->next=graph[u];graph[u]=x;}voidinit{intfor(inti=0;i<MAXROUTE;{intnum,tot,scanf("%d%d%d",&num,&type,for(intj=0;j<tot;j++)scanf("%d",&List[j]);for(intj=0;j<tot;j++)for(intk=j+1;k<tot;addEdge(List[j],List[k],k-j,num,route[num][0]=for(intj=0;j<tot;j++)route[num][j+1]=}}voidMinimalSwap{for(inti=0;i<MAXN;i++)minswap[i]=infinity;memset(used,false,sizeof(used));minswap[source]=0;for(inti=0;i<MAXN;{intmin=infinity,for(intj=0;j<MAXN;if(!used[j]&&minswap[j]<{min=minswap[j];minp=}if(min==infinity)return;used[minp]=true;Tgraph*x=graph[minp];while(x!=NULL){if(minswap[minp]+1<minswap[x->p])minswap[x->p]=minswap[minp]+1;x=x->}}}voidMinimalCost{for(inti=0;i<MAXN;i++)mincost[i]=infinity;memset(used,false,sizeof(used));mincost[source]=0;for(inti=0;i<MAXN;{intmin=infinity,for(intj=0;j<MAXN;if(!used[j]&&mincost[j]<{min=mincost[j];minp=}if(min==infinity)return;used[minp]=true;Tgraph*x=graph[minp];while(x!=NULL){if(minswap[minp]+1==minswap[x->if(mindist[minp]+x->len==mindist[x->p])if(mincost[minp]+x->cost<mincost[x->{mincost[x->p]=mincost[minp]+x->cost;previous[x->p]=minp;preEdge[x->p]=}x=x->}}}voidMinimalDist{for(inti=0;i<MAXN;i++)mindist[i]=infinity;memset(used,false,sizeof(used));mindist[source]=0;for(inti=0;i<MAXN;{intmin=infinity,for(intj=0;j<MAXN;if(!used[j]&&mindist[j]<{min=mindist[j];minp=}if(min==infinity)return;used[minp]=true;Tgraph*x=graph[minp];while(x!=NULL){if(minswap[minp]+1==minswap[x->p])if(mindist[minp]+x->len<mindist[x->p])mindist[x->p]=mindist[minp]+x->len;x=x->next;}}}voidfind(intu,intv,intnum,int{for(inti=1;i<route[num][0];if(route[num][i]==u&&route[num][i+len]=={for(intj=i;j<i+len;j++)printf("S%04d->",route[num][j]);printf("S%04d\n",route[num][i+len]);}}voidbacktrace(int{if(v==source)return;backtrace(previous[v]);printf("\nTime%d:TakeBusLine%03d\n",time,preEdge[v]->num);printf("Route :");find(previous[v],v,preEdge[v]->num,preEdge[v]->}int{printf("StartStation:");scanf("%d",&source);printf("TargetStation:");scanf("%d",&target);printf("\n");printffreopen("bus.txt","r",stdin);init();MinimalSwapMinimalDist();MinimalCost//freopen("result.txt","w",printf ysisReportprintf(" MinimalSwapis%d\n",minswap[target]-1);printf(" MinimalCostis%d\n",mincost[target]);printf MinimalTimeis%d\n",mindist[target]*3+(minswap[target]-1)*time=0;backtrace(target);return}附录const=constconst=const=const const const const ;constintgaptime[2][2]= {{10,12},{14,8}};structTgraph{ p,swap,dist,cost,num; route[MAXROUTE+1][MAXN]; boolused[MAXN];bool_used[MAXN][2]; N,source,target,voidaddEdge(intu,intv,intswp,intcost,intlen,int{Tgraph*x=newTgraph;x->p=v;x->swap=swp;x->dist=len;x->cost=cost;x->num=x->next=graph[u];graph[u]=x;}intgetcost(inttype,int{if(type==2)return1;elseif(len<=20)return1;if(len<=40)return2;return}voidInitBus(char{freopen(filename,"r",stdin);intList[MAXN];for(inti=0;i<MAXROUTE;{intnum,tot,scanf("%d%d%d",&num,&type,for(intj=0;j<tot;j++)scanf("%d",&List[j]);for(intj=0;j<tot;j++)for(intk=j+1;k<tot;addEdge(List[j],List[k],1,getcost(type,k-j),(k-j)*6,route[num][0]=for(intj=0;j<tot;j++)route[num][j+1]=}}voidInitSubway1(char{freopen(filename,"r",stdin);intList[MAXSTATION1][10];for(inti=0;i<MAXSTATION1;{scanf("%d",scanf("%d",for(intj=0;j<List[i][0];j++)scanf("%d",&List[i][j+for(intj=0;j<=List[i][0];j++)stop[0][i][j]=}for(inti=0;i<MAXSTATION1;{for(inta=0;a<List[i][0];for(intb=a+1;b<List[i][0];{addEdge(List[i][a+1],List[i][b+1],0,0,0,-addEdge(List[i][b+1],List[i][a+1],0,0,0,-}for(intj=i+1;j<MAXSTATION1;j++)for(inta=0;a<List[i][0];a++)for(intb=0;b<List[j][0];{addEdge(List[i][a+1],List[j][b+1],1,3,(j-i)*5,-addEdge(List[j][b+1],List[i][a+1],1,3,(j-i)*5,-}}}voidInitSubway2(char{freopen(filename,"r",stdin);intList[MAXSTATION2][10];for(inti=0;i<MAXSTATION2;{scanf("%d",scanf("%d",for(intj=0;j<List[i][0];j++)scanf("%d",&List[i][j+for(intj=0;j<=List[i][0];j++)stop[1][i][j]=}for(inti=0;i<MAXSTATION2;{for(inta=0;a<List[i][0];for(intb=a+1;b<List[i][0];{addEdge(List[i][a+1],List[i][b+1],0,0,0,-addEdge(List[i][b+1],List[i][a+1],0,0,0,-}for(intj=i+1;j<MAXSTATION2;j++)for(inta=0;a<List[i][0];a++)for(intb=0;b<List[j][0];{addEdge(List[i][a+1],List[j][b+1],1,3,(j-i)*5,-addEdge(List[j][b+1],List[i][a+1],1,3,(j-i)*5,-}}}voidMinimalSwap{for(inti=0;i<MAXN;i++)minswap[i]=infinity;memset(used,false,sizeof(used));minswap[source]=0;for(inti=0;i<MAXN;{intmin=infinity,for(intj=0;j<MAXN;if(!used[j]&&minswap[j]<{min=minswap[j];minp=}if(min==infinity)return;used[minp]=true;Tgraph*x=graph[minp];while(x!=NULL){if(minswap[minp]+x->swap<minswap[x->p])minswap[x->p]=minswap[minp]+x->swap;x=x->}}}voidMinimalCost{for(inti=0;i<MAXN;i++)mincost[i]=infinity;memset(used,false,sizeof(used));mincost[source]=0;for(inti=0;i<MAXN;{intmin=infinity,for(intj=0;j<MAXN;if(!used[j]&&mincost[j]<{min=mincost[j];minp=}if(min==infinity)return;used[minp]=true;Tgraph*x=while(x!={if(minswap[minp]+x->swap==minswap[x->p])if(mincost[minp]+x->cost<mincost[x->p])mincost[x->p]=mincost[minp]+x->cost;x=x->next;}}}intcode(Tgraph{if(x->swap==0)return0;if(x->num>0)return0;elsereturn}voidMinimalDist{for(inti=0;i<MAXN;i++)mindist[i][0]=mindist[i][1]=infinity;memset(_used,false,sizeof(_used));mindist[source][0]=0;_used[source][0]=true;mindist[source][1]=0;_used[source][1]=Tgraph*x=graph[source];while(x!=NULL){if(minswap[source]+x->swap==minswap[x->p])if(mincost[source]+x->cost==mincost[x->p])if(mindist[source][0]+x->dist<mindist[x->p][code{mindist[x->p][code(x)]=mindist[source][0]+x->dist;previous[x->p][code(x)]=source*2;preEdge[x->p][code(x)]=}x=x->}for(inti=0;i<MAXN*2;{intmin=infinity,for(intj=0;j<MAXN;j++)for(ints=0;s<2;s++)if(!_used[j][s]&&mindist[j][s]<{min=mindist[j][s];minp=j*2+}if(min==infinity)_used[minp/2][minp%2]=x=graph[minp/while(x!={intdelta=x->dist+gaptime[minp%2][code(x)];if(x->swap==0)delta=0;if(minswap[minp/2]+x->swap==minswap[x->p])if(mincost[minp/2]+x->cost==mincost[x->p])if(mindist[minp/2][minp%2]+delta<mindist[x->p][code{//printf("%d%d%d%d\n",minp/2,minp%2,x->p,code(x-//printf("%d%d\n",min,mindist[x->p][code(x)]=mindist[minp/2][minp%2]+delta;previous[x->p][code(x)]=minp;preEdge[x->p][code(x)]=}x=x->}}}voidfind(intu,intv,intnum,int{for(inti=1;i<route[num][0];if(route[num][i]==u&&route[num][i+len]=={for(intj=i;j<i+len;j++)printf("S%04d->",route[num][j]);printf("S%04d\n",route[num][i+len]);}}intcommon(inta,intb,int{if(line==-{for(inti=0;i<MAXSTATION1;{}}{

intsum=for(intj=1;j<=stop[0][i][0];if(stop[0][i][j]==a||stop[0][i][j]==b)sum++;if(sum==2)returnstation[0][i];for(inti=0;i<MAXSTATION2;{intsum=for(intj=1;j<=stop[1][i][0];if(stop[1][i][j]==a||stop[1][i][j]==b)if(sum==2)return}}}voidbacktrace(intv,int{if(v==source)backtrace(previous[v][s]/2,previous[v][s]%2);if(preEdge[v][s]->swap==printf("\nTime%d:FromS%04dtoS%04dthroughSubwayStationtime,previous[v][s]/2,v,common(previous[v][s]/2,v,preEdge[v][s]->if(preEdge[v][s]->num<{}{printf("\nTime%d:TakeBusLine%03d\n",time,preEdge[v][s]->num);printf("Route :");find(previous[v][s]/2,v,preEdge[v][s]->num,preEdge[v][s]->dist/}}intmin(inta,int{returna<b?a:}intminstate(int{if(mindist[v][0]<mindist[v][1])return0;elseif(mindist[v][0]>mindist[v][1])return1;}int{printf("StartStation:");scanf("%d",&source);printf("TargetStation:");scanf("%d",&target);printf("\n");printfInitBus("bus.txt");InitSubway1("subway1.txt");InitSubway2//freopen("result.txt","w",stdout);MinimalSwap();MinimalCost();MinimalDistprintf("**ysisReportprintf(" MinimalSwapis%d\n",minswap[target]-1);printf(" MinimalCostis%d\n",mincost[target]);prin