trans.cpp

交通信息咨询系统

//#include"c1.h"
#include<iostream>
#include<fstream>
#include<string>
using namespace std;
#define INFINITY 9999999
#define MAX_VERTEX_NUM 30
typedef int VRType;
typedef struct ArcCell{
	VRType  adj;
	string info;
	float start;
	float end;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct{
	int serial;
	string name;
}VertexType;
typedef bool PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct{
	VertexType vexs[MAX_VERTEX_NUM];
    AdjMatrix arcs;
	int vexnum,arcnum;
}MGraph;   
typedef struct{
	float ins;
	int rout;
}Shortist;
int final[MAX_VERTEX_NUM];   //final[v]为TRUE时，即已求得最短路径
int shortt[MAX_VERTEX_NUM];  //最短路径上顶点的顺序
int n=0;                     //最短路径上顶点个数
int D[MAX_VERTEX_NUM];       //最短路径集，D【i】表示从v0到i当前求得最短路径。
int finalt[MAX_VERTEX_NUM];
int shorttime[MAX_VERTEX_NUM];
int nt=0;
Shortist Dt[MAX_VERTEX_NUM];
int LocateVex(MGraph&G,string v)
{   int i;
	for(i=0;i<G.vexnum;i++)
	if(v==G.vexs[i].name)
	return i;
}
void create(MGraph&G)
{   
	ifstream infile("expenses.txt",ios::in);
	if(!infile)
	{cerr<<"open instance.txt error!"<<endl;
	exit(1);
	}
	infile>>G.vexnum>>G.arcnum;
int i,j,k,w;
string v1,v2;
for(i=0;i<G.vexnum;++i) 
{
G.vexs[i].serial=i;
infile>>G.vexs[i].name;
}
for(i=0;i<G.vexnum;i++) 
    for(j=0;j<G.vexnum;j++) 
	{
    G.arcs[i][j].adj=INFINITY;
	G.arcs[j][i].adj=INFINITY;
    G.arcs[i][j].info='0';
    G.arcs[j][i].info='0';
	}
for(k=0;k<G.arcnum;k++)
{
infile>>v1;
infile>>v2;
infile>>w;
i=LocateVex(G,v1);j=LocateVex(G,v2);
G.arcs[i][j].adj=w;
G.arcs[j][i].adj=w;
//if(IncInfo)Input(*G.arcs[v1][v2].info);
}
infile.close();
}  
void get_time(MGraph&G)
{   int i,j,k,m;
    float t1,t2;
    string s1,s2;
	ifstream infile("time.txt",ios::in);
	if(!infile)
	{cerr<<"open instance.txt error!"<<endl;
	exit(1);
	}
	for(k=0;k<G.vexnum;k++)
    for(m=0;m<G.vexnum;m++)
	{
	 G.arcs[k][m].end=INFINITY;
     G.arcs[k][m].start=INFINITY;
	 G.arcs[m][k].end=INFINITY;
     G.arcs[m][k].start=INFINITY;
	}
	for(k=0;k<2*G.arcnum;k++)
	{
	infile>>s1;
	i=LocateVex(G,s1);
	infile>>s2;
	j=LocateVex(G,s2);
	infile>>t1;
	infile>>t2;   
	G.arcs[i][j].start=t1;
	G.arcs[i][j].end=t2;
	}
}
void shortesttime(MGraph G,int v0,PathMatrix &p)
{
	int v,i,w,min,j,k,vt,vs;
	vt=v0;
	for(v=0;v<G.vexnum;++v)
	{
     finalt[v]=0;
	 if(G.arcs[v0][v].start<INFINITY)
    Dt[v].ins=G.arcs[v0][v].end-G.arcs[v0][v].start;
	 else Dt[v].ins=INFINITY;
	 Dt[v].rout=v0;
     for(w=0;w<G.vexnum;++w) p[v][w]=false;
     if(Dt[v].ins<INFINITY){p[v][v0]=true;p[v][v]=true;}
	}
    Dt[v0].ins=0;finalt[v0]=1; shorttime[0]=v0;   //初始化
	//开始主循环
   for(i=1;i<G.vexnum;++i)
   { vs=v;
	 min=INFINITY;
     for(w=0;w<G.vexnum;++w)
     if(!finalt[w])
     if(Dt[w].ins<min){v=w;min=Dt[w].ins;}
     finalt[v]=1;    	  
	 if(v!=vs)
	 {
	 shorttime[i]=v;
	 nt++;
	 }
	 vt=Dt[v].rout;
     for(w=0;w<G.vexnum;++w)
     if(!finalt[w]&&(Dt[v].ins+G.arcs[v][w].end-G.arcs[vt][v].end)<Dt[w].ins&&G.arcs[v][w].end!=INFINITY&&G.arcs[v][w].start>=G.arcs[vt][v].end)
	 {
      Dt[w].ins=Dt[v].ins+G.arcs[v][w].end-G.arcs[vt][v].end;
	  Dt[w].rout=v;
      for(j=0;j<G.vexnum;++j)
      p[w][j]=p[v][j];
      p[w][w]=true;
	 }
   }
}

void shortestpath_DIJ(MGraph G,int v0,PathMatrix &p)
{int v,i,w,min,j,k,vs;
	for(v=0;v<G.vexnum;++v)
	{
     final[v]=0;
     D[v]=G.arcs[v0][v].adj;
     for(w=0;w<G.vexnum;++w) p[v][w]=false;
     if(D[v]<INFINITY){p[v][v0]=true;p[v][v]=true;}
	}
    D[v0]=0;final[v0]=1; shortt[0]=v0;   //初始化
	//开始主循环
   for(i=1;i<G.vexnum;++i)
   { vs=v;
	 min=INFINITY;
     for(w=0;w<G.vexnum;++w)
     if(!final[w])
     if(D[w]<min){v=w;min=D[w];}
     final[v]=1;
	 if(vs!=v){
     shortt[i]=v;
	 n++;}
     for(w=0;w<G.vexnum;++w)
     if(!final[w]&&(min+G.arcs[v][w].adj)<D[w])
	 {
      D[w]=min+G.arcs[v][w].adj;
      for(j=0;j<G.vexnum;++j)
	  {
      p[w][j]=p[v][j];
      p[w][w]=true;
      }
	 }
   }
  
} 
int judge(MGraph&G,string &v)
{   int i;
    bool h=true;
	for(i=0;i<G.vexnum;i++)
	if(G.vexs[i].name==v)
	h=false;
    return h;
}
void enter(MGraph&G,string &v,int m)
{string s;
int i;
bool t;
t=true;
for(i=0;i<10&&t;i++)
{
if(m==1)cout<<"please enter the start station you want to seach:"<<endl;
if(m==2)cout<<"please enter the ending station you want to seach:"<<endl;
cin>>s;
if(!judge(G,s))
t=false;
else cout<<"this station is not existed.please enter after you check."<<endl;
}
v=s;
}

void insert(MGraph&G)
{   int inser,inser0,inserarc,i,j,m,k,w;
    float w1,w2,w3,w4;
    string v1,v2,v3;
	inser0=0;
	cout<<"enter the number you want to insert:"<<endl;
    cin>>inser;
	cout<<"enter the name of the railway station one by one:"<<endl; 
	for(k=0;k<inser;k++)
	{
	cin>>v3;
	if(judge(G,v3))
	{G.vexs[G.vexnum+k].name=v3;
     inser0++;
	}
	}
    G.vexnum+=inser0;
	m=G.vexnum;
	for(i=0;i<inser0;i++)
	for(j=0;j<m;j++)
	{
	G.arcs[m-inser0+i][j].adj=INFINITY;
	G.arcs[m-inser0+i][j].start=INFINITY;
	G.arcs[m-inser0+i][j].end=INFINITY;
	G.arcs[j][m-inser0+i].adj=INFINITY;
	G.arcs[j][m-inser0+i].start=INFINITY;
	G.arcs[j][m-inser0+i].end=INFINITY;
    G.arcs[m-inser0+i][j].info='0';
	}
	cout<<"enter the arcnumbers you want to insert:"<<endl;
    cin>>inserarc;
	G.arcnum+=inserarc;
	cout<<"the arc length one by one:"<<endl;
	for(k=0;k<inserarc;k++)
	{
	 cout<<"enter the name of the two railway station:"<<endl;
     cin>>v1;
     cin>>v2;
	 cout<<"enter the instance:"<<endl;
     cin>>w;
     i=LocateVex(G,v1);j=LocateVex(G,v2);
     G.arcs[i][j].adj=w;
     G.arcs[j][i].adj=w;
	cout<<"enter the start time and the end time:"<<endl;
	cin>>w1;
	cin>>w2;
    G.arcs[i][j].start=w1;
	G.arcs[i][j].end=w2;
	cout<<"the return route the start time and the end time:"<<endl;
	cin>>w3;
	cin>>w4;
    G.arcs[j][i].start=w3;
    G.arcs[j][i].end=w4;
	}
}
void deletee(MGraph&G)
{   int inser,i,j,w,k,dele;
    string v;
	dele=0;
	cout<<"please enter the number you want to delete:"<<endl;
    cin>>inser;
	cout<<"enter the name of the railway station one by one:"<<endl; 
    for(i=0;i<inser;i++)
	{
	cin>>v;
	j=LocateVex(G,v);
    for(w=0;w<G.vexnum;w++)
	if(G.arcs[j][w].adj<INFINITY&&G.arcs[j][w].adj!=0)
		dele++;
	    for(w=0;w<j;w++)
		for(k=j;k<(G.vexnum-i-1);k++)
		{
			G.arcs[w][k].adj=G.arcs[w][k+1].adj;
            G.arcs[w][k].start=G.arcs[w][k+1].start;
			G.arcs[w][k].end=G.arcs[w][k+1].end;		    
		}
		for(w=j;w<(G.vexnum-i-1);w++)
		for(k=0;k<j;k++)
		{   G.arcs[w][k].adj=G.arcs[w+1][k].adj;
			G.arcs[w][k].start=G.arcs[w+1][k].start;
			G.arcs[w][k].end=G.arcs[w+1][k].end;
		}
		for(w=j;w<(G.vexnum-i-1);w++)
		for(k=j;k<(G.vexnum-i-1);k++)			
		{G.arcs[w][k].adj=G.arcs[w+1][k+1].adj;
		G.arcs[w][k].start=G.arcs[w+1][k+1].start;
		G.arcs[w][k].end=G.arcs[w+1][k+1].end;}
		G.arcs[G.vexnum-i-1][G.vexnum-i-1].adj=INFINITY;
        G.arcs[G.vexnum-i-1][G.vexnum-i-1].start=INFINITY;
		G.arcs[G.vexnum-i-1][G.vexnum-i-1].end=INFINITY;
        for(k=j;k<(G.vexnum-i-1);k++)
		G.vexs[k].name=G.vexs[k+1].name;
 
	}
	G.arcnum-=dele;
	G.vexnum-=inser;
}
void save(MGraph&G)
{   int i,j;
	ofstream outfile("expenses.txt",ios::out);
	if(!outfile)
	{cerr<<"open instance.txt error!"<<endl;
	exit(1);
	}
    ofstream outfile1("time.txt",ios::out);
	if(!outfile1)
	{cerr<<"open time.txt error!"<<endl;
	exit(1);
	}
    outfile<<G.vexnum<<' '<<G.arcnum<<endl;
	for(i=0;i<G.vexnum;++i) 
    outfile<<G.vexs[i].name<<' ';
	outfile<<endl;
    for(i=0;i<G.vexnum;i++) 
    for(j=0;j<i;j++) 
    if(G.arcs[i][j].adj<INFINITY&&G.arcs[i][j].adj!=0)
    outfile<<G.vexs[i].name<<' '<<G.vexs[j].name<<' '<<G.arcs[i][j].adj<<' ';
    for(i=0;i<G.vexnum;++i) 
	for(j=0;j<G.vexnum;++j) 
	if(G.arcs[i][j].start<INFINITY)
    outfile1<<G.vexs[i].name<<' '<<G.vexs[j].name<<' '<<G.arcs[i][j].start<<' '<<G.arcs[i][j].end;
	outfile.close();
	outfile1.close();
}
void output(MGraph&G,int v1,PathMatrix &p)
{    int w,k;
	if(final[v1])
	 {
	 for(w=0;w<(n+1);++w)
	 {
	 k=shortt[w];
	 if(p[v1][k])
		 cout<<G.vexs[k].name<<' ';
	 }
	 cout<<endl;
	 cout<<"the instance is:"<<D[v1]<<endl;
	}
}
void outputime(MGraph&G,int v0,int v1,PathMatrix &p)
{
	int w,k,t,t0,kt,kt1;
	float expense;
	expense=0;
	float time;
	int ts[10];
	t=0;
	if(finalt[v1])
	 {
	 for(w=0;w<(nt+1);++w)
	 {
	 k=shorttime[w];
	 if(p[v1][k])
	 {   cout<<G.vexs[k].name<<" ";
	     ts[t]=k;
         t++;
	 }
	 }
	 cout<<endl;
	 t0=ts[1];
	 cout<<"the name of station"<<" "<<"the starting time"<<" "<<"the ending time"<<"  the unit:hour"<<endl;
	 for(w=0;w<t-1;w++)
	 {   
		 kt=ts[w];
	     kt1=ts[w+1];
		 expense+=G.arcs[kt][kt1].adj;
		 cout<<G.vexs[kt].name<<"   "<<G.arcs[kt][kt1].start<<' '<<G.vexs[kt1].name<<"  "<<G.arcs[kt][kt1].end<<endl;
	 }
	 cout<<"the starting:"<<G.vexs[v0].name<<endl;
	 cout<<"the ending:"<<G.vexs[v1].name<<endl;
	 cout<<"the train go at :"<<G.arcs[v0][t0].start<<" oclock"<<endl;
	 time=Dt[v1].ins;
	 cout<<"the time you spend is:"<<time<<" hour"<<endl;
	 cout<<"the expense you spend is:"<<expense<<" yuan"<<endl;
	}
	else cout<<"the fewest route can't be found!"<<endl;
}
int main()
{   string s1,s2;
    int i,j;
	int chance;
	bool s;
	PathMatrix p;
    PathMatrix p1;
	MGraph G;
	create(G);
	get_time(G);
	while(s)
	{
	cout<<"what's do you want to do: 1 插入车站 2 删除车站 3 搜索路线 4. 存盘 5 退出"<<endl;
	cin>>chance;
	switch(chance)
	{
     case 1:insert(G);break;
	 case 2:deletee(G);break;
	 case 3:
     enter(G,s1,1);
	 enter(G,s2,2);
     i=LocateVex(G,s1);
	 j=LocateVex(G,s2);
	 cout<<"the route of the fewest instance:"<<endl;
     shortestpath_DIJ(G,i,p);
     output(G,j,p);
	 cout<<"the route of the least time:"<<endl;
     shortesttime(G,i,p1);
     outputime(G,i,j,p1);
 	 break;
	 case 4:save(G);break;
	 case 5:s=false;break;
	}
	}
	return 0;
}