#include<string>
#include<conio.h>
#include<stdlib.h>
//using namespace std;
//頂點，邊和圖類型
#define MAXVTXNUM 20  //圖中頂點數的最大值
typedef struct{
 char name[20];    //該頂點代表的景點的名稱
 char info[20];    //景點的信息
}VertexType;    //頂點類型
typedef struct{
 int lengh;
 int ivex,jvex;
}EdgeType;
typedef struct EdgeNode{
 EdgeType elem;
 EdgeNode *ilink,*jlink;
}EdgeNode,*EdgePtr;

typedef struct{
 VertexType data;
 EdgePtr firstEdge;
}VNode;

typedef struct{
 VNode Adjmulist[MAXVTXNUM];
 int vexNum,edgeNum;
}GraphType;

GraphType ga;//多重鄰接表
EdgeNode edge[MAXVTXNUM];

//圖的基本操作
void InitGraph(GraphType &g){
 g.vexNum=g.edgeNum=0;
}

int LocateVex(GraphType &g,char *uname,int &i){
 int j;
 for(j=0;j<20 ;j++){
  if(!strcmp(g.Adjmulist[j].data.name,uname)){
   i=j;
   return 0;
  }
 }
  return 1;
 
}


void GetVex(GraphType g,int i,VertexType &v){
 v=g.Adjmulist[i].data;
}

EdgePtr FirstEdge(GraphType g,int vi){
 return g.Adjmulist[vi].firstEdge;
}


void NextEdge(GraphType g,int vi,EdgePtr p,int &vj,EdgePtr &q){
 if(p->elem.ivex==vi){
  q=p->ilink;
  vj=p->elem.jvex;
 }
 else {
  q=p->jlink;
  vj=p->elem.ivex;
 }
}////????

void InsertVex(GraphType &g,VertexType v){
 static f=0;
 strcpy(g.Adjmulist[f].data.name,v.name);
 //printf("%s",g.Adjmulist[f].data.name);
 strcpy(g.Adjmulist[f].data.info,v.info);
 f++;
}

/*void InsertEdge(GraphType &g,EdgeType e){
 EdgePtr p;
 p=(EdgePtr)malloc(sizeof(EdgeNode));
 p->elem=e;
 p->ilink=FirstEdge(g,e.ivex);
 p->jlink=FirstEdge(g,e.jvex);
 g.Adjmulist[e.ivex].firstEdge=g.Adjmulist[e.jvex].firstEdge=p;
}*/

//void DeleteVex(GraphType &g,Vertextype v);

//void DeleteEdge(GraphType &g,EgdeType e);
void LinkEdge(GraphType &g,EdgeNode *s){
 int m,j;
 for(m=0;m<g.edgeNum;m++){
  for(j=m+1;j<g.edgeNum;j++){
   if((edge[m].elem.ivex==edge[j].elem.ivex)||(edge[m].elem.ivex==edge[j].elem.jvex))
   {
    edge[m].ilink=&edge[j];
   break;
   }
  }
 }
 for(m=0;m<g.edgeNum;m++){
  for(j=m+1;j<g.edgeNum;j++){
   if((edge[m].elem.jvex==edge[j].elem.ivex)||(edge[m].elem.jvex==edge[j].elem.jvex))
   {
    edge[m].jlink=&edge[j];
    break;
   }
  }
 }
}//連接邊的函數
void LinkfirstEdge(GraphType &g,EdgeNode *s){
 int i,j;
 for(i=0;i<g.vexNum;i++){
  for(j=0;j<g.edgeNum;j++){
   if((i==edge[j].elem.ivex)||(i==edge[j].elem.jvex)){
    g.Adjmulist[i].firstEdge=&edge[j];
    break;
   }
  }
 }
}//把第一條邊連上

 

//路徑類型
typedef struct{
 int vx,vy;
}Edge;
typedef struct{
 Edge edges[MAXVTXNUM];
 int len;
}PathType;
typedef struct{
 char vertices[MAXVTXNUM][20];
 int num;
}PType;


void InitPath(PathType &pa){
 pa.len=0;
}

void copyPath(PathType &p1,PathType p2){
 int i;
 for(i=0;i<p2.len;i++){
  p1.edges[i].vx=p2.edges[i].vx;
  p1.edges[i].vy=p2.edges[i].vy;
 }
 p1.len=p2.len;
}

void InsertPath(PathType &pa,int v,int w){
 pa.edges[pa.len].vx=v;
 pa.edges[pa.len].vy=w;
 pa.len++;
}

int PathLength(PathType pa){
 return pa.len;
}

void OutPath(GraphType g ,PathType pa,PType &vtxes){
   int  m=0,i;
   VertexType vtx;
 for(i=0;i<pa.len;i++){
  GetVex(g,pa.edges[i].vx,vtx);
  strcpy(vtxes.vertices[m++],vtx.name);
 }
 

 GetVex(g,pa.edges[pa.len-1].vy,vtx);
 strcpy(vtxes.vertices[m],vtx.name);
 vtxes.num=m;
}


//主程序和其它算法

void Initialization()
{
void CreatGraph(GraphType &g,FILE *f);

 FILE *fp;
    if((fp=fopen("D:\\test.txt","r"))==NULL){

        printf("\n文件未找到!");
        exit(1);
 }
 CreatGraph(ga,fp);
 printf("初始化成功。\n");
 printf("按S查看景點信息，按V查找路徑，Q退出。\n");
}


void ReadCommand(char &cmd)
{
 do{
 cmd=getche();
 }while(cmd!='s'&&cmd!='S'&&cmd!='v'&&cmd!='V'&&cmd!='q'&&cmd!='Q');
}//過濾一下

void PrintPath(PType &spath,int pathlen){
 int s;
 printf("路徑長度是:%d\n",pathlen);
 printf("所經景點為:");
 for(s=0;s<=spath.num;s++){
  printf("%s,",spath.vertices[s]);
 }

}

void Interpret(char cmd)
{
void GetShortestPath(GraphType g,char *sname,char *tname, int &pathLength,PType &PathInfo);

 char sn[20],sname[20],tname[20];
 int sv,pathlen;
 PType spath;
 switch(cmd){
 case's':
 case'S':
  printf("請輸入景點名稱：");
  scanf("%s",sn);
  LocateVex(ga,sn,sv);
  printf("景點信息:%s \n",ga.Adjmulist[sv].data.info);
  break;
 case'v':
 case'V':
  printf("請輸入始點:");
  scanf("%s",sname);
        printf("請輸入終點:");
  scanf("%s" ,tname);
  GetShortestPath(ga,sname,tname,pathlen,spath);
  PrintPath(spath,pathlen);
 
  printf("\n");
  break;
 case'Q':
 case'q': 
  exit(0);
  break;
 }
}
 

void CreatGraph(GraphType &g,FILE *f)
{
 VertexType v;
 EdgeType e;
 int k,i,s=0;
 InitGraph(g);
 fscanf(f,"%d%d",&g.vexNum,&g.edgeNum);
 for(i=0;i<g.vexNum;i++){
  fscanf(f,"%s%s",&v.name,&v.info);
  InsertVex(g,v);
 }

 for(k=0;k<g.edgeNum;k++){
  fscanf(f,"%d%d%d",&e.ivex,&e.jvex,&e.lengh);
  //printf("%d,%d,%d\n",e.ivex,e.jvex,e.lengh);
  if(e.lengh)
  edge[s++].elem=e;
  //InsertEdge(g,e);
 }
 LinkEdge(g,edge);
 LinkfirstEdge(g,edge);
}

void GetShortestPath(GraphType g,char *sname,char *tname, int &pathLength,PType &PathInfo)
{
  void ShortestPath(GraphType g,int st,int nd,int &pathLength,PType &PathInfo);
 int sv,tv;
 LocateVex(g,sname,sv);
 LocateVex(g,tname,tv);
 ShortestPath(g,sv,tv,pathLength,PathInfo);
}
void InitSet(int *p){
 int m;
 for(m=0;m<20;m++)
  p[m]=9999;
}
void PutInSet(int s,int *ss){
 static p=0;
  ss[p++]=s;//保存最短路徑序列
}

int minval(GraphType &g,int *i){
 int s,t,w;
 t=i[0];
 for(s=0;s<g.vexNum;s++){
  if(t>i[s])
   t=i[s];
 }
 for(w=0;w<g.vexNum;w++){
  if(t==i[w])
     return w;
 }
}//返回最小的


   
int InSet(int t,int *s){
 int i;
 for(i=0;i<20;i++)
 {
  if(t==s[i])
   return 0;
 }
 return 1;
}

void ShortestPath(GraphType g,int st,int nd,int &pathLength,PType &PathInfo)
{
 int dist[MAXVTXNUM],i,adjvex,min,found,v,w;
 PathType path[MAXVTXNUM];
 EdgePtr p,q;
 int ss[20];
    //int pp;

 for(i=0;i<g.vexNum;i++)
 {
  dist[i]=9999;
  InitPath(path[i]);
 }
 p=FirstEdge(g,st);
 while(p){
  NextEdge(g,st,p,adjvex,q);//////////??????
  dist[adjvex]=p->elem.lengh;
  InsertPath(path[adjvex],st,adjvex);//
  p=q;
 }
 found=0;
 InitSet(ss);PutInSet(st,ss);

 //for(pp=0;pp<g.vexNum;pp++)      
 //printf("%d\n",dist[pp]);

 //getch();    
 while(!found){
  min=minval(g,dist);

  //printf("min is %d\n",min);

  if(min==nd) found=1;
  
  else{
   v=min;PutInSet(v,ss);
   p=FirstEdge(g,v);
   while(p){
    NextEdge(g,v,p,w,q);
    if(InSet(w,ss)&&(dist[v]+p->elem.lengh)<dist[w])
    {
     dist[w]=dist[v]+p->elem.lengh;

     //printf("\ndist[v] is %d",dist[v]);
     //printf("\np->elem.lengh is %d",p->elem.lengh);
     //printf("\ndist[w] is %d",dist[w]);
     //getch();

     copyPath(path[w],path[v]);//？
     //printf("\npath[v] longth is %d",path[v].len);
     InsertPath(path[w],v,w);
    }
    p=q;
   }//while(p)
   dist[v]=9999;
  }//else
 }//while(!found)
 pathLength=dist[nd];
 //printf("路徑長為%d",dist[nd]);
 //printf("此時長度為%d\n",path[nd].len);
 //getch();
 OutPath(g,path[nd],PathInfo);
} 
void begain(){
 printf("****************************×圖的遍歷程序×************************************");
 
}
void main()
{
 char cmd;
 begain();
 Initialization();
 do{
  ReadCommand(cmd);
  Interpret(cmd);
 }while(cmd!='q'&&cmd!='Q');
}