#include <iostream> #include <string.h> #include <iomanip> #include <math.h> /* run this program using the console pauser or add your own getch, system("pause") or input loop */ using namespace std;  #define length 30 typedef char lname[length]; typedef struct {lname a,b; }name;                                               typedef struct  {int a;  int *b; }dada; typedef struct {dada *c; }twnum; typedef struct {twnum *w; }save;  int location2(twnum *tw,int num1,int a,int b); void route(save *yw,twnum *tw,name *ming,int bpoint[],int num1); void copy(int isi,int rr,int r,int pp,save *yw);  void dos(int i,int j,int point[],int mark[],twnum *tw,twnum *uw,save *yw,int rr,int &r,int isi,int &pp); int locate(lname aa,name *ming,int num1); int main(int argc, char** argv) { 	cout<<"请输入地点的个数以及两地点可以通路的路径条数"<<endl; 	int num1 ,num2,r,f; 	cin>>num1>>num2; 	 	int mark[num1],point[num1],bpoint[num1];                  //重要的辅助数组  	for(int i=0;i<num1;i++) 	{mark[i]=0;point[i]=0;bpoint[i]=(num1-1); 	} 	 	name *ming; 	ming=new name[num1];  	cout<<"请分别输入地点的真实名称和简称"<<endl; 	cout<<"例如 :“鸳鸯湖  v1 ”"<<endl; 	for(int i=0;i<num1;i++) 	cin>>ming[i].a>>ming[i].b; 	 	twnum *tw,*uw,*gw;  	save *yw;                            	tw=new twnum[num1]; 	uw=new twnum[num1]; 	yw=new save[num1]; 	gw=new twnum[num1]; 	for(int i=0;i<num1;i++) 	{tw[i].c=new dada[num1]; 	 uw[i].c=new dada[num1-1]; 	} 	for(int i=0;i<num1;i++) 	for(int j=0;j<num1;j++) 	tw[i].c[j].a=0; 	 	for(int i=0;i<num1;i++) 	for(int j=0;j<num1-1;j++)     uw[i].c[j].a=1008612; 	  	 	lname aa,bb; 	int cc,d,e,pp; 	cout<<"请分别输入可以直接连通的两个地点简称及其之间的距离"<<endl; 	cout<<"例如：”v1 v2 100 “"<<endl; 	for(int i=0;i<num2;i++)                                    {cin>>aa>>bb>>cc;     d=locate(aa,ming,num1);                                         e=locate(bb,ming,num1); 	tw[d].c[e].a=cc; 	tw[e].c[d].a=cc; 	point[d]++; 	point[e]++; 	bpoint[d]--; 	bpoint[e]--;}                                          	 	for(int i=0;i<num1;i++) 	{yw[i].w=new twnum[bpoint[i]]; 	 gw[i].c=new dada[bpoint[i]];}              	 	for(int i=0;i<num1;i++) 	for(int j=0;j<bpoint[i];j++) 	yw[i].w[j].c=new dada[length]; 	 	for(int i=0;i<num1;i++) 	for(int j=0;j<bpoint[i];j++) 	for(int k=0;k<length;k++) 	yw[i].w[j].c[k].b=new int[num1]; 	 	 	for(int i=0;i<num1;i++) 	tw[i].c[i].a=1008611; 	 	for(int i=0;i<num1;i++) 	for(int j=0,k=0,l=0;j<num1;j++) 	{                                       	  if(tw[i].c[j].a==0) {gw[i].c[l].a=j;l++;continue ;}                     	  if(tw[i].c[j].a==1008611) {continue;}       else uw[i].c[k].a=j,k++; 	}; 	 	for(int i=0;i<num1;i++) 	for(int j=0;j<bpoint[i];j++) 	for(int k=0;k<length;k++) 	for(int g=0;g<num1;g++) 	yw[i].w[j].c[k].b[g]=10086; 	  	                                                         	for(int i=0;i<num1;i++) 	{int rr=-1;int isi=i;     for(int j=0;j<num1;j++)       { 	if(tw[i].c[j].a==1008611) continue;                                	if(tw[i].c[j].a==0) 	{rr++;f++;pp=0;r=0;    	for(int hi=0;hi<num1;hi++) 	mark[hi]=0; 	 dos(i,j,point,mark,tw,uw,yw,rr,r,isi,pp);     }     }                                                      }    route(yw,tw,ming,bpoint,num1); 	return 0; }  void dos(int i,int j,int point[],int mark[],twnum *tw,twnum *uw,save *yw,int rr,int &r,int isi,int &pp) {yw[isi].w[rr].c[r].b[pp]=i;                        pp++;                                                     mark[i]=1;         int td1,td3,hh,kk;  td3=i;  td1=point[i];                                                 int ia;  if(tw[td3].c[j].a!=0) yw[isi].w[rr].c[r].b[pp]=j,r++,pp--,mark[i]=0,copy(isi,rr,r,pp,yw);  else    {for(ia=0;ia<td1;ia++)  {if(mark[uw[td3].c[ia].a]!=0){continue;}  i=uw[td3].c[ia].a;  dos(i,j,point,mark,tw,uw,yw,rr,r,isi,pp);  }  } if(ia==td1) mark[td3]=0,pp--;  }  void copy(int isi,int rr,int r,int pp,save *yw) {for(int i=0;i<pp;i++)  yw[isi].w[rr].c[r].b[i]=yw[isi].w[rr].c[r-1].b[i];  pp++; }   int locate(lname aa,name *ming,int num1)  {int i;   for(i=0;i<num1;i++)   { if(strcmp(ming[i].b,aa)==0)     return i;   }   return -1; }   void route(save *yw,twnum *tw,name *ming,int bpoint[],int num1) { lname aa,bb;   int lx1=0,lx2=0,a,b,c[num1];  cout<<"请分别输入起始地点和终点的简称按enter键结束"<<endl;  cout<<"起始点简称：";cin>>aa;   cout<<"终点简称";cin>>bb;  cout<<endl;   a=locate(aa,ming,num1);  b=locate(bb,ming,num1);  if(a==b){cout<<"您输入了两个相同地点，请确认两不同地点后再次输入"<<endl;route(yw,tw,ming,bpoint,num1);}  location2(tw,num1,a,b);  if(tw[a].c[b].a==0)   {	int lc=0;     cout<<"您输入的两个地点不可以直接通达"<<endl;     cout<<"以下是可参考路线及其相应的路程"<<endl; 	int zb; 	zb=location2(tw,num1,a,b); 	cout<<endl; 	for(int k=0;k<length&&yw[a].w[zb].c[k].b[0]!=10086;k++)     { 	for(int g=0;g<num1;g++) 	 c[g]=yw[a].w[zb].c[k].b[g]; 	      for(int g=0;g<num1;g++) 	 if(c[g]==b)       {cout<<"参考路线"<<k+1<<":";      lx1=c[0];lx2=c[1];lc=tw[lx1].c[lx2].a; 	  for(int uu=0;uu<num1;uu++)       {if(c[uu]==b){cout<<bb;break;} 	   cout<<ming[c[uu]].a<<"--->"; 	   if(uu>1) {lc=lc+tw[lx1].c[lx2].a;lx1=lx2,lx2=c[uu];}       }       lc=lc+tw[lx2].c[b].a;       cout<<"总路程："<<lc<<"米"<<endl;     }     cout<<endl;    }  }  else   {cout<<"路径为："<<endl;  cout<<ming[a].a<<"--->"<<ming[b].a<<' '<<"总路程："<<tw[a].c[b].a<<"米"<<endl;  }  }  int location2(twnum *tw,int num1,int a,int b) {int t=-1;  for(int k=0;k<num1;k++)  {if(tw[a].c[k].a==0)t++;  if(k==b) return t;  }  return -1; }