zuoye.cpp

交通路线最优路径寻找程序

	strcpy(shenyang[1].toolname,"火车1712");
	shenyang[1].usetime=22;
	shenyang[1].money=93;
	strcpy(shenyang[2].cityname,"haerbin");
	strcpy(shenyang[2].toolname,"火车1302");
	shenyang[2].usetime=7;
	shenyang[2].money=40;
	strcpy(shenyang[3].cityname,"haerbin");
	strcpy(shenyang[3].toolname,"t238");
	shenyang[3].usetime=5;
	shenyang[3].money=50;
	strcpy(shenyang[4].cityname,"shijiazhuang");
	strcpy(shenyang[4].toolname,"火车t182");
	shenyang[4].usetime=12.5;
	shenyang[4].money=115;
	strcpy(shenyang[5].cityname,"dalian");
	strcpy(shenyang[5].toolname,"火车2623");
	shenyang[5].usetime=5;
	shenyang[5].money=40;
	strcpy(shenyang[6].cityname,"qinhuangdao");
	strcpy(shenyang[6].toolname,"火车1051");
	shenyang[6].usetime=5;
	shenyang[6].money=35;
	strcpy(shenyang[7].cityname,"beijing");
	strcpy(shenyang[7].toolname,"飞机ca1601");
	shenyang[7].usetime=1.2;
	shenyang[7].money=280;
	strcpy(shenyang[8].cityname,"guangzhou");
	strcpy(shenyang[8].toolname,"飞机cz6302");
	shenyang[8].usetime=4.6;
	shenyang[8].money=1020;
	strcpy(shenyang[9].cityname,"guangzhou");
	strcpy(shenyang[9].toolname,"飞机");
	shenyang[9].usetime=3.2;
	shenyang[9].money=1140;
	strcpy(shenyang[10].cityname,"tianjin");
	strcpy(shenyang[10].toolname,"飞机3u8861");
	shenyang[10].usetime=1.2;
	shenyang[10].money=690;
	strcpy(shenyang[11].cityname,"shanghai");
	strcpy(shenyang[11].toolname,"飞机9c8839");
	shenyang[11].usetime=2.2;
	shenyang[11].money=620;
	strcpy(shenyang[12].cityname,"baotou");
	strcpy(shenyang[12].toolname,"飞机cz6456");
	shenyang[12].usetime=1.5;
	shenyang[12].money=1000;
	strcpy(shenyang[13].cityname,"haerbin");
	strcpy(shenyang[13].toolname,"飞机mf8046");
	shenyang[13].usetime=0.9;
	shenyang[13].money=460;
	strcpy(shenyang[14].cityname,"shijiazhuang");
	strcpy(shenyang[14].toolname,"飞机vd8327");
	shenyang[14].usetime=1.4;
	shenyang[14].money=840;
	strcpy(shenyang[15].cityname,"");
	strcpy(shenyang[15].toolname,"");
	shenyang[15].usetime=0;
	shenyang[15].money=0;


    strcpy(shijiazhuang[0].cityname,"shijiazhuang");
	strcpy(shijiazhuang[0].toolname,"");
	shijiazhuang[0].usetime=0;
	shijiazhuang[0].money=0;
	strcpy(shijiazhuang[1].cityname,"shenyang");           //石家庄连接的城市
	strcpy(shijiazhuang[1].toolname,"飞机vd8327");
	shijiazhuang[1].usetime=1.4;
	shijiazhuang[1].money=840;
	strcpy(shijiazhuang[2].cityname,"dalian");
	strcpy(shijiazhuang[2].toolname,"飞机eu2214");
	shijiazhuang[2].usetime=1.3;
	shijiazhuang[2].money=680;
	strcpy(shijiazhuang[3].cityname,"qinhuangdao");
	strcpy(shijiazhuang[3].toolname,"飞机zh9961");
	shijiazhuang[3].usetime=0.8;
	shijiazhuang[3].money=240;
	strcpy(shijiazhuang[4].cityname,"dalian");
	strcpy(shijiazhuang[4].toolname,"飞机cz6954");
	shijiazhuang[4].usetime=1.2;
	shijiazhuang[4].money=760;
	strcpy(shijiazhuang[5].cityname,"shanghai");
	strcpy(shijiazhuang[5].toolname,"飞机fm9139");
	shijiazhuang[5].usetime=1.8;
	shijiazhuang[5].money=990;
	strcpy(shijiazhuang[6].cityname,"guangzhou");
	strcpy(shijiazhuang[6].toolname,"飞机cz3131");
	shijiazhuang[6].usetime=2.5;
	shijiazhuang[6].money=680;
	strcpy(shijiazhuang[7].cityname,"shanghai");
	strcpy(shijiazhuang[7].toolname,"火车k233");
	shijiazhuang[7].usetime=18.5;
	shijiazhuang[7].money=175;
	strcpy(shijiazhuang[8].cityname,"tianjin");
	strcpy(shijiazhuang[8].toolname,"火车t182");
	shijiazhuang[8].usetime=4.5;
	shijiazhuang[8].money=55;
	strcpy(shijiazhuang[9].cityname,"qinhuangdao");
	strcpy(shijiazhuang[9].toolname,"火车t182");
	shijiazhuang[9].usetime=0;
	shijiazhuang[9].money=0;
	strcpy(shijiazhuang[10].cityname,"shenyang");
	strcpy(shijiazhuang[10].toolname,"火车t182");
	shijiazhuang[10].usetime=12.5;
	shijiazhuang[10].money=115;
	strcpy(shijiazhuang[11].cityname,"haerbin");
	strcpy(shijiazhuang[11].toolname,"火车t238");
	shijiazhuang[11].usetime=16.5;
	shijiazhuang[11].money=165;
	strcpy(shijiazhuang[12].cityname,"shijiazhuang");
	strcpy(shijiazhuang[12].toolname,"");
	shijiazhuang[12].usetime=0;
	shijiazhuang[12].money=0;
	strcpy(shijiazhuang[13].cityname,"shijiazhuang");
	strcpy(shijiazhuang[13].toolname,"");
	shijiazhuang[13].usetime=0;
	shijiazhuang[13].money=0;
	strcpy(shijiazhuang[14].cityname,"");
	strcpy(shijiazhuang[14].toolname,"");
	shijiazhuang[14].usetime=0;
	shijiazhuang[14].money=0;

	strcpy(qinhuangdao[0].cityname,"qinhuangdao");
	strcpy(qinhuangdao[0].toolname,"");
	qinhuangdao[0].usetime=0;
	qinhuangdao[0].money=0;
	strcpy(qinhuangdao[1].cityname,"baotou");           //秦皇岛连接的城市
	strcpy(qinhuangdao[1].toolname,"火车1712");
	qinhuangdao[1].usetime=17;
	qinhuangdao[1].money=65;
    strcpy(qinhuangdao[2].cityname,"haerbin");
	strcpy(qinhuangdao[2].toolname,"火车1302");
	qinhuangdao[2].usetime=13;
	qinhuangdao[2].money=75;
	strcpy(qinhuangdao[3].cityname,"haerbin");
	strcpy(qinhuangdao[3].toolname,"火车t238");
	qinhuangdao[3].usetime=9;
	qinhuangdao[3].money=90;
	strcpy(qinhuangdao[4].cityname,"shijiazhuang");
	strcpy(qinhuangdao[4].toolname,"火车t182");
	qinhuangdao[4].usetime=8;
	qinhuangdao[4].money=85;
	strcpy(qinhuangdao[5].cityname,"dalian");
	strcpy(qinhuangdao[5].toolname,"火车t131");
	qinhuangdao[5].usetime=7;
	qinhuangdao[5].money=55;
	strcpy(qinhuangdao[6].cityname,"beijing");
	strcpy(qinhuangdao[6].toolname,"飞机cz6361");
	qinhuangdao[6].usetime=0.9;
	qinhuangdao[6].money=280;
	strcpy(qinhuangdao[7].cityname,"beijing");
	strcpy(qinhuangdao[7].toolname,"飞机kn2937");
	qinhuangdao[7].usetime=0.8;
	qinhuangdao[7].money=350;
	strcpy(qinhuangdao[8].cityname,"tianjin");
	strcpy(qinhuangdao[8].toolname,"飞机sc4717");
	qinhuangdao[8].usetime=1;
	qinhuangdao[8].money=580;
    strcpy(qinhuangdao[9].cityname,"shanghai");
	strcpy(qinhuangdao[9].toolname,"飞机fm9141");
	qinhuangdao[9].usetime=1.8;
	qinhuangdao[9].money=1040;
	strcpy(qinhuangdao[10].cityname,"baotou");
	strcpy(qinhuangdao[10].toolname,"飞机zh9695");
	qinhuangdao[10].usetime=0.7;
	qinhuangdao[10].money=410;
	strcpy(qinhuangdao[11].cityname,"shijiazhuang");
	strcpy(qinhuangdao[11].toolname,"飞机zh9961");
	qinhuangdao[11].usetime=0.8;
	qinhuangdao[11].money=240;
	strcpy(qinhuangdao[12].cityname,"");
	strcpy(qinhuangdao[12].toolname,"");
	qinhuangdao[12].usetime=0;
	qinhuangdao[12].money=0;


}                                     //上边函数构建出交通网络图



void findaway(char begin[15],char over[15],char welike[15])     //搜索最优路径函数
{
	double linksum[9];                //用来保存各个数组最小花费的数组
	for(int j=0;j<9;j++)
	  linksum[j]=10000;               //初始化
	char last[15];                    //保存起始城市名字
    	strcpy(last,begin);
	storecity first[11],second[11],third[11],forth[11],fifth[11],sixth[11],seventh[11],eighth[11],ninth[11];//用来保存路线

	//下边是将各结构数组赋予特殊形式首位作为标志位，其sum值为-1表示结构数组为空，其余位的城市为""时表示未赋值
	strcpy(first[0].city,"");
	strcpy(first[0].tool,"");
	first[0].sum=-1;
	strcpy(first[1].city,"");
	strcpy(first[1].tool,"");
	first[1].sum=0;
	
	for (int i=2;i<11;i++)
	{
		first[i]=first[1];
		second[i]=first[1];
		third[i]=first[1];
		forth[i]=first[1];
		fifth[i]=first[1];
		sixth[i]=first[1];
		seventh[i]=first[1];
		eighth[i]=first[1];
		ninth[i]=first[1];
	}

	second[0]=third[0]=forth[0]=fifth[0]=sixth[0]=seventh[0]=eighth[0]=ninth[0]=first[0];
	second[1]=third[1]=forth[1]=fifth[1]=sixth[1]=seventh[1]=eighth[1]=ninth[1]=first[1];
	                                           //赋值结束
    while (strcmp(begin,over))                 //现在节点是否为终点，是则不用继续找了，否则继续找。
	{
		
		storecity oneminute1,oneminute2,oneminute3,oneminute4,oneminute5,oneminute6,oneminute7,oneminute8,oneminute9;//用来保存每条存储连下一个最小耗费城市节点
		char next1[15],next2[15],next3[15],next4[15],next5[15],next6[15],next7[15],next8[15],next9[15];//用来存下一最小节点城市名字
		
		if(!strcmp(welike,"money"))
		{
		if(!empty(first))                                    //存储链不空时
		{
			
			strcpy(next1,lastcity(first).city);              //找到该链最后一节点城市名
		    oneminute1=searchsmallmoney(next1);              //找寻下1最小代价节点
			linksum[0]=oneminute1.sum+lastcity(first).sum;   //二者代价加和，以进行比较各链路代价
			
		}
		else                                                 //存储链空时
		{
			oneminute1=searchsmallmoney(last);
			linksum[0]=oneminute1.sum;
			
			goto line1;                                      //因为每次只添加一条空存储链，所以下面不必再寻求空存储链节点了
		}
		if(!empty(second))
		{
			
			strcpy(next2,lastcity(second).city);
			oneminute2=searchsmallmoney(next2);
			linksum[1]=oneminute2.sum+lastcity(second).sum;

		}
        else
		{
			oneminute2=searchsmallmoney(last);
			linksum[1]=oneminute2.sum;
			
			goto line1;
		}
		if(!empty(third))
		{
			
			strcpy(next3,lastcity(third).city);
			oneminute3=searchsmallmoney(next3);
			linksum[2]=oneminute3.sum+lastcity(third).sum;
		
		}
        else
		{
			oneminute3=searchsmallmoney(last);
			linksum[2]=oneminute3.sum;
		
			goto line1;
		}
		if(!empty(forth))
		{
			
			strcpy(next4,lastcity(forth).city);
			oneminute4=searchsmallmoney(next4);
			linksum[3]=oneminute4.sum+lastcity(forth).sum;
			
		}
        else
		{
			oneminute4=searchsmallmoney(last);
			linksum[3]=oneminute4.sum;
			
			goto line1;
		}
		if(!empty(fifth))
		{
			
			strcpy(next5,lastcity(fifth).city);
			oneminute5=searchsmallmoney(next4);
			linksum[4]=oneminute5.sum+lastcity(fifth).sum;
			
		}
        else
		{
			oneminute5=searchsmallmoney(last);
			linksum[4]=oneminute5.sum;
		
			goto line1;
		}
		if(!empty(sixth))
		{
			
			strcpy(next6,lastcity(sixth).city);
			oneminute6=searchsmallmoney(next6);
			linksum[5]=oneminute6.sum+lastcity(sixth).sum;
			
		}
        else
		{
			oneminute6=searchsmallmoney(last);
			linksum[5]=oneminute6.sum;
			
			goto line1;
		}
		if(!empty(seventh))
		{
		
			strcpy(next7,lastcity(seventh).city);
			oneminute7=searchsmallmoney(next7);
			linksum[6]=oneminute7.sum+lastcity(seventh).sum;
			
		}
        else
		{
			oneminute7=searchsmallmoney(last);
			linksum[6]=oneminute7.sum;
			
			goto line1;
		}
		if(!empty(eighth))
		{
			
			strcpy(next8,lastcity(eighth).city);
			oneminute8=searchsmallmoney(next8);
			linksum[7]=oneminute8.sum+lastcity(eighth).sum;
			
		}
        else
		{
			oneminute8=searchsmallmoney(last);
			linksum[7]=oneminute8.sum;
			
			goto line1;
		}
		if(!empty(ninth))
		{
			
			strcpy(next9,lastcity(ninth).city);
			oneminute9=searchsmallmoney(next9);
			linksum[8]=oneminute9.sum+lastcity(ninth).sum;
			
		}
        else
		{
			oneminute9=searchsmallmoney(last);
			linksum[8]=oneminute9.sum;
			
			goto line1;
		}
line1:
		double min=1000000;                                  //选取最小消耗链路
		int flag=-1;
		for(int s=0;s<9;s++)
			if(min>linksum[s])
			{
				min=linksum[s];
				flag=s;
			}
		if(flag==0)
		{
			int u,e;
			for(u=1;strcmp(first[u].city,"");u++)
				;
			first[u]=oneminute1;
			begin=oneminute1.city;	
			for( e=0;strcmp(outcity[e].city,"");e++)        //标记已经走过了
				;
			strcpy(outcity[e].city,oneminute1.city);
			first[0].sum=0;                                    //存储链已经非空了
		}
		else if(flag==1)
		{
			int u,e;
			for(u=1;strcmp(second[u].city,"");u++)
				;
			second[u]=oneminute2;
			begin=oneminute2.city;	
			for(e=0;strcmp(outcity[e].city,"");e++)
				;
			strcpy(outcity[e].city,oneminute2.city);
			second[0].sum=0;
		}
		else if(flag==2)
		{
			int u,e;
			for(u=1;strcmp(third[u].city,"");u++)
				;
			third[u]=oneminute3;
			begin=oneminute3.city;	
			for(e=0;strcmp(outcity[e].city,"");e++)
				;
			strcpy(outcity[e].city,oneminute3.city);
			third[0].sum=0;
		}
		else if(flag==3)
		{
			int u,e;
			for(u=1;strcmp(forth[u].city,"");u++)
				;
			forth[u]=oneminute4;
			begin=oneminute4.city;	
			for( e=0;strcmp(outcity[e].city,"");e++)
				;
			strcpy(outcity[e].city,oneminute4.city);
			forth[0].sum=0;
		}
		else if(flag==4)
		{
			int u,e;
			for(u=1;strcmp(fifth[u].city,"");u++)
				;
			fifth[u]=oneminute5;
			begin=oneminute5.city;	
			for(e=0;strcmp(outcity[e].city,"");e++)