graph.h

传统的Dijkstra 算法无疑是解决一般最短路径问题的最优算法

		for(i=1;i<=countt0;i++)
		for(j=1;j<=fn[change(t[i])];j++)
			if(fv[change(t[i])][j]==false)
				{
					fv[change(t[i])][j]=true;
					k=findpathin(y+countt1,f[change(t[i])][j]);
                    for(n=countt1+1;n<=countt1+k;n++)
					{
						strcpy(posy[n],t[i]);
				        yf[n]=j;
					}
					countt1+=k;
					if(countt1>5800)goto b;
				}
b:
	for(i=1;i<=counth1;i++)
		for(j=1;j<=countt1;j++)
			if((strcmp(r[i],y[j])==0)&&strcmp(prer[i],posy[j])&&strcmp(prer[i],r[i])&&strcmp(y[j],posy[j]))
				if(ispath(vhead,e[change(prer[i])][re[i]],prer[i]))//vhead和e[change(prer[i])][re[i]]是在h[i]上符合方向的点
				if(ispath(e[change(prer[i])][re[i]],f[change(posy[j])][yf[j]],r[i]))//e[i][]和f[j]是符合线路r上方向的站点
				if(ispath(f[change(posy[j])][yf[j]],vtail,posy[j]))
				{
					time=0;
					sta=0;
					money=0;
					//先求所用时间，费用
                     k=LocateVertex(vhead);
				     end=LocateVertex(vtail);
					 linenum[0]=change(prer[i]);
					 linenum[1]=change(r[i]);
					 linenum[2]=change(posy[j]);
					 bef=k;
						 for(p=graph[k].firstarc;p&&strcmp(graph[k].vertexname,e[change(prer[i])][re[i]]);)
						 if(strcmp(p->lname,prer[i])==0)//沿着h[i]走但是没有走到公共站点e[change(prer[i])][re[i]]
						 {
							 if(p->adjvertex==bef){p=p->nextarc;continue;}
							bef=k;
							time+=3;
							k=p->adjvertex;
							p=graph[k].firstarc;
							sta++;
						 }
						 else p=p->nextarc;
						 //到达公共站点e[i][u]，即e[change(prer[i])][re[i]]
						if(!p)continue;
						time+=6;
						k=p->adjvertex;
						money+=judgemoney(sta,ticket[linenum[0]]);
						sta=0;
						bef=k;
                        //到达公共站点e[change(prer[i])][re[i]]后,通过线路r[i]走到公共站点f[j][v],即f[change(posy[j])][yf[j]]
						 for(p=graph[k].firstarc;p&&strcmp(graph[k].vertexname,f[change(posy[j])][yf[j]]);)
						 if(strcmp(p->lname,r[i])==0)//沿着r[i]走但是没有走到公共站点f[change(posy[j])][yf[j]]
						 {
							 if(p->adjvertex==bef){p=p->nextarc;continue;}
							bef=k;
							time+=3;							
							k=p->adjvertex;
							p=graph[k].firstarc;
							sta++;
						 }
						 else p=p->nextarc;
						 //到达公共站点f[j][v]，即f[change(posy[j])][yf[j]]   
						 if(!p)continue;//2
						 
						time+=6;
						k=p->adjvertex;
						money+=judgemoney(sta,ticket[linenum[1]]);
						sta=0;
						bef=k;
                        //沿着t[i],即posy[j]走到终点
						   for(p=graph[k].firstarc;p;)
							if(strcmp(p->lname,posy[j])==0)
							{
							    if(p->adjvertex==bef){p=p->nextarc;continue;}
							    bef=k;
								time+=3;
							    k=p->adjvertex;
								if(k==end)break;
								p=graph[k].firstarc;
								sta++;
							}
							else p=p->nextarc;

							if(!p)continue;
							money+=judgemoney(sta,ticket[linenum[2]]);
				cout<<vhead<<"->"<<prer[i]<<"->"<<e[change(prer[i])][re[i]]<<"->"<<r[i]<<"->"<<f[change(posy[j])][yf[j]]
					<<"->"<<posy[j]<<"->"<<vtail<<" "<<"所用时间为："<<time<<"分钟,费用为："<<money<<"元"<<endl;
			    count++;
				}//if(ispath(f[change(posy[j])][yf[j]],vtail,posy[j]))
	return count;
}


int GRaph::twiceandthreepathtime(ElemType h[100],ElemType t[100],int counth0,int countt0,int counth1,int countt1)
{//counth0为从起点发出的线路数，countt0为进入终点的线路数
	ARcType *p;
	int bef,i,j,k,n,end,linenum[3],sta,money,time,count=0;
    int money1,mintime=infinity;
	ElemType prer[6000],posy[6000];//记录r[i]前一条路h[i];y[i]后面一条路t[i]
    ElemType vhead2,prer2,eij2,ri2,fij2,posy2,vtail2;//记录时间最短的线路
    int re[6000],yf[6000];//记录r[i]出自f[][j],y[i]进入e[][j]

	for(i=0;i<600;i++)
		for(j=0;j<100;j++)
			ev[i][j]=fv[i][j]=false;

	counth1=countt1=0;
	for(i=1;i<=counth0;i++)
		for(j=1;j<=en[change(h[i])];j++)
		if(!ev[change(h[i])][j])
		{
           ev[change(h[i])][j]=true;
			k=findpathout(r+counth1,e[change(h[i])][j],h[i]);//f[i][j]为线路i会从站点j出来,e[i][j]为线路i会进入站点j
            for(n=counth1+1;n<=counth1+k;n++)
			{
				strcpy(prer[n],h[i]);
				re[n]=j;
			}
            counth1+=k;
			if(counth1>5800)goto a;
		}

a:	for(i=1;i<=countt0;i++)
		for(j=1;j<=fn[change(t[i])];j++)
			if(fv[change(t[i])][j]==false)
				{
					fv[change(t[i])][j]=true;
					k=findpathin(y+countt1,f[change(t[i])][j]);
                    for(n=countt1+1;n<=countt1+k;n++)
					{
						strcpy(posy[n],t[i]);
				        yf[n]=j;
					}
					countt1+=k;
					if(countt1>5800)goto b;
				}


b:
	for(i=1;i<=counth1;i++)
		for(j=1;j<=countt1;j++)
			if((strcmp(r[i],y[j])==0)&&strcmp(prer[i],posy[j])&&strcmp(prer[i],r[i])&&strcmp(y[j],posy[j]))
				if(ispath(vhead,e[change(prer[i])][re[i]],prer[i]))//vhead和e[change(prer[i])][re[i]]是在h[i]上符合方向的点
				if(ispath(e[change(prer[i])][re[i]],f[change(posy[j])][yf[j]],r[i]))//e[i][]和f[j]是符合线路r上方向的站点
				if(ispath(f[change(posy[j])][yf[j]],vtail,posy[j]))
				{					
					time=0;
					sta=0;
					money=0;
					//先求所用时间，费用
                     k=LocateVertex(vhead);
				     end=LocateVertex(vtail);
					 linenum[0]=change(prer[i]);
					 linenum[1]=change(r[i]);
					 linenum[2]=change(posy[j]);
					 bef=k;
						 for(p=graph[k].firstarc;p&&strcmp(graph[k].vertexname,e[change(prer[i])][re[i]]);)
						 if(strcmp(p->lname,prer[i])==0)//沿着h[i]走但是没有走到公共站点e[change(prer[i])][re[i]]
						 {
							 if(p->adjvertex==bef){p=p->nextarc;continue;}
							bef=k;
							time+=3;
							k=p->adjvertex;
							p=graph[k].firstarc;
							sta++;
						 }
						 else p=p->nextarc;
						 //到达公共站点e[i][u]，即e[change(prer[i])][re[i]]
						if(!p)continue;
						time+=6;
						k=p->adjvertex;
						money+=judgemoney(sta,ticket[linenum[0]]);
						sta=0;
						bef=k;
                        //到达公共站点e[change(prer[i])][re[i]]后,通过线路r[i]走到公共站点f[j][v],即f[change(posy[j])][yf[j]]
						 for(p=graph[k].firstarc;p&&strcmp(graph[k].vertexname,f[change(posy[j])][yf[j]]);)
						 if(strcmp(p->lname,r[i])==0)//沿着r[i]走但是没有走到公共站点f[change(posy[j])][yf[j]]
						 {
							 if(p->adjvertex==bef){p=p->nextarc;continue;}
							bef=k;
							time+=3;
							k=p->adjvertex;
							p=graph[k].firstarc;
							sta++;
						 }
						 else p=p->nextarc;
						 //到达公共站点f[j][v]，即f[change(posy[j])][yf[j]]   
						 if(!p)continue;//2
						 
						time+=6;
						k=p->adjvertex;
						money+=judgemoney(sta,ticket[linenum[1]]);
						sta=0;
						bef=k;
                        //沿着t[i],即posy[j]走到终点
						   for(p=graph[k].firstarc;p;)
							if(strcmp(p->lname,posy[j])==0)
							{
							 if(p->adjvertex==bef){p=p->nextarc;continue;}
							bef=k;
								time+=3;
							    k=p->adjvertex;
								if(k==end)break;
								p=graph[k].firstarc;
								sta++;
							}
							else p=p->nextarc;

							if(!p)continue;
								money+=judgemoney(sta,ticket[linenum[2]]);

			    count++;
				if(time<mintime)
				{
					mintime=time;
					money1=money;
					strcpy(vhead2,vhead);
					strcpy(prer2,prer[i]);
					strcpy(eij2,e[change(prer[i])][re[i]]);
					strcpy(ri2,r[i]);
					strcpy(fij2,f[change(posy[j])][yf[j]]);
					strcpy(posy2,posy[j]);
					strcpy(vtail2,vtail);
				}
			
			}
				if(count)
				{
					cout<<vhead2<<"->"<<prer2<<"->"<<eij2<<"->"<<ri2<<"->"<<fij2
					<<"->"<<posy2<<"->"<<vtail2<<" "<<"所用时间为："<<mintime<<"分钟,费用为："<<money1<<"元。"<<endl;
					return 1;
				}
				
	return 0;
}


int GRaph::twiceandthreepathsometime(ElemType h[100],ElemType t[100],int counth0,int countt0,int counth1,int countt1)
{//counth0为从起点发出的线路数，countt0为进入终点的线路数
	ARcType *p;
	int bef,index,i,j,k,n,end,linenum[3],fasttime[5],sta,money,time,count=0;
    int money1[5];
	ElemType prer[6000],posy[6000];//记录r[i]前一条路h[i];y[i]后面一条路t[i]
    ElemType vhead2[5],prer2[5],eij2[5],ri2[5],fij2[5],posy2[5],vtail2[5];//记录时间最短的线路
    int re[6000],yf[6000];//记录r[i]出自f[][j],y[i]进入e[][j]

	for(i=0;i<600;i++)
		for(j=0;j<100;j++)
			ev[i][j]=fv[i][j]=false;
     for(i=0;i<5;i++)
		 fasttime[i]=infinity;

	counth1=countt1=0;
	for(i=1;i<=counth0;i++)
		for(j=1;j<=en[change(h[i])];j++)
		if(!ev[change(h[i])][j])
		{
           ev[change(h[i])][j]=true;
			k=findpathout(r+counth1,e[change(h[i])][j],h[i]);//f[i][j]为线路i会从站点j出来,e[i][j]为线路i会进入站点j
            for(n=counth1+1;n<=counth1+k;n++)
			{
				strcpy(prer[n],h[i]);
				re[n]=j;
			}
            counth1+=k;
			if(counth1>5800)goto a;
		}

a:	for(i=1;i<=countt0;i++)
		for(j=1;j<=fn[change(t[i])];j++)
			if(fv[change(t[i])][j]==false)
				{
					fv[change(t[i])][j]=true;
					k=findpathin(y+countt1,f[change(t[i])][j]);
                    for(n=countt1+1;n<=countt1+k;n++)
					{
						strcpy(posy[n],t[i]);
				        yf[n]=j;
					}
					countt1+=k;
					if(countt1>5800)goto b;
				}


b:
	for(i=1;i<=counth1;i++)
		for(j=1;j<=countt1;j++)
			if((strcmp(r[i],y[j])==0)&&strcmp(prer[i],posy[j])&&strcmp(prer[i],r[i])&&strcmp(y[j],posy[j]))
				if(ispath(vhead,e[change(prer[i])][re[i]],prer[i]))//vhead和e[change(prer[i])][re[i]]是在h[i]上符合方向的点
				if(ispath(e[change(prer[i])][re[i]],f[change(posy[j])][yf[j]],r[i]))//e[i][]和f[j]是符合线路r上方向的站点
				if(ispath(f[change(posy[j])][yf[j]],vtail,posy[j]))
				{					
					time=0;
					sta=0;
					money=0;
					//先求所用时间，费用
                     k=LocateVertex(vhead);
				     end=LocateVertex(vtail);
					 linenum[0]=change(prer[i]);
					 linenum[1]=change(r[i]);
					 linenum[2]=change(posy[j]);
					 bef=k;
						 for(p=graph[k].firstarc;p&&strcmp(graph[k].vertexname,e[change(prer[i])][re[i]]);)
						 if(strcmp(p->lname,prer[i])==0)//沿着h[i]走但是没有走到公共站点e[change(prer[i])][re[i]]
						 {
							 if(p->adjvertex==bef){p=p->nextarc;continue;}
							bef=k;
							time+=3;
							k=p->adjvertex;
							p=graph[k].firstarc;
							sta++;
						 }
						 else p=p->nextarc;
						 //到达公共站点e[i][u]，即e[change(prer[i])][re[i]]
						if(!p)continue;
						time+=6;
						k=p->adjvertex;
						money+=judgemoney(sta,ticket[linenum[0]]);
						sta=0;
						bef=k;
                        //到达公共站点e[change(prer[i])][re[i]]后,通过线路r[i]走到公共站点f[j][v],即f[change(posy[j])][yf[j]]
						 for(p=graph[k].firstarc;p&&strcmp(graph[p->adjvertex].vertexname,f[change(posy[j])][yf[j]]);)
						 if(strcmp(p->lname,r[i])==0)//沿着r[i]走但是没有走到公共站点f[change(posy[j])][yf[j]]
						 {
							 if(p->adjvertex==bef){p=p->nextarc;continue;}
							bef=k;
							time+=3;
							k=p->adjvertex;
							p=graph[k].firstarc;
							sta++;
						 }
						 else p=p->nextarc;
						 //到达公共站点f[j][v]，即f[change(posy[j])][yf[j]]   
						 if(!p)continue;//2
						 
						time+=6;
						k=p->adjvertex;
						money+=judgemoney(sta,ticket[linenum[1]]);
						sta=0;
						bef=k;
                        //沿着t[i],即posy[j]走到终点
						   for(p=graph[k].firstarc;p;)
							if(strcmp(p->lname,posy[j])==0)
							{		
							if(p->adjvertex==bef){p=p->nextarc;continue;}
							bef=k;
								time+=3;
							    k=p->adjvertex;
								if(k==end)break;
								p=graph[k].firstarc;
								sta++;
							}
							else p=p->nextarc;

							if(!p)continue;
								money+=judgemoney(sta,ticket[linenum[2]]);

			    count++;
				index=num(fasttime,time,count);
				if(index!=-1)
				{
					money1[index]=money;
					strcpy(vhead2[index],vhead);
					strcpy(prer2[index],prer[i]);
					strcpy(eij2[index],e[change(prer[i])][re[i]]);
					strcpy(ri2[index],r[i]);
					strcpy(fij2[index],f[change(posy[j])][yf[j]]);
					strcpy(posy2[index],posy[j]);
					strcpy(vtail2[index],vtail);
				}
			
			}
				if(count)
				{
					cout<<"换乘两次的最快几条路线为："<<endl;
					if(count>5)count=5;
					for(i=0;i<count;i++)
				     cout<<vhead2[i]<<"->"<<prer2[i]<<"->"<<eij2[i]<<"->"<<ri2[i]<<"->"<<fij2[i]<<"->"<<posy2[i]<<"->"<<vtail2[i]<<" "<<"所用时间为："<<fasttime[i]<<"分钟,费用为："<<money1[i]<<"元"<<endl;
				     return 1;
				}
		
	return 0;
}