实验六034100549.cpp

数据结构常用算法

#include "iostream.h"
#define infinity 1000
class railnet{
public:
	railnet();
	void shortpath(int,int);
private:
	int arcs[6][6];
	char* place[7];
	int vexnum;
};
railnet::railnet()
{
	vexnum=6;
	*place="宁波";
	*(place+1)="杭州";
	*(place+2)="上海";
	*(place+3)="北京";
	*(place+4)="武汉";
	*(place+5)="哈尔滨";
	*(place+6)=" ";
	for(int k=0;k<6;k++) 
		for(int r=0;r<6;r++)
			arcs[r][k]=infinity;
	arcs[0][2]=10;arcs[2][0]=10;
	arcs[0][4]=30;arcs[4][0]=30;
	arcs[0][5]=100;arcs[5][0]=100;
	arcs[1][2]=5;arcs[2][1]=5;
	arcs[2][3]=50;arcs[3][2]=50;
	arcs[3][5]=10;arcs[5][3]=10;
	arcs[4][3]=20;arcs[3][4]=20;
	arcs[4][5]=60;arcs[5][4]=60;
}
void railnet::shortpath(int v0,int vt)
{
	int p[6][5];
	int d[6];
	int final[6];
	int min,v,w,i;
	for(v=0;v<vexnum;++v){
		final[v]=0;d[v]=arcs[v0][v];
		for(w=0;w<4;++w)p[v][w]=6;
		if(d[v]<infinity){p[v][0]=v0;p[v][1]=v;}
		p[v][4]=2;
	}
	d[v0]=0;final[v0]=1;
	for(i=1;i<vexnum;++i){
		min=infinity;
		for(w=0;w<vexnum;++w)
			if(!final[w])
				if(d[w]<min){v=w;min=d[w];}
		final[v]=1;
		if(v==vt){
			cout<<"Your shortest train's route is: ";
			for(int x=0;x<4;x++)
			{
				int y=p[v][x];
				if(y!=6)cout<<"->"<<place[y];
			}
			cout<<"\nAnd the total distance is "<<d[v]<<"km";
		return;
		}
		for(w=0;w<vexnum;w++)
			if(!final[w]&&(min+arcs[v][w]<d[w])){
				d[w]=min+arcs[v][w];
				int z=p[v][4];
				for(int a=0;a<5;a++)p[w][a]=p[v][a];
				p[w][z]=w;p[w][4]++;
			}
	}
	for(i=1;i<vexnum;++i)
		if(i==vt)
			cout<<"Sorry!The railway between "<<place[v0]<<" and "<<place[vt]<<" is building.:)";
}
main()
{
	int v0,vt;
	cout<<"欢迎进入铁路查询系统!\n（0）宁波，（1）杭州，（2）上海，（3）北京，（4）武汉，（5）哈尔滨\n";
	cout<<"Please input the code of your start station:";
	cin>>v0;
	cout<<"\nAnd your aim station:";
	cin>>vt;cout<<endl;
	railnet t;
	t.shortpath(v0,vt);
	cout<<endl;
	return 0;
}