//本程序最好在VC++中运行，但这是C程序，在TC中，显示结果会出现乱码，TC不支持汉字
#include "string.h"
#include "stdio.h"
#include "malloc.h"
#include "stdlib.h"
#define Max 20000
#define NUM 9
typedef struct ArcCell
{
 int adj; 
}ArcCell;
typedef struct VertexType
{
 int number; 
 char *sight; 
 char *description;
}VertexType;  

typedef struct
{
 VertexType vex[NUM];
 ArcCell arcs[NUM][NUM];
 int vexnum,arcnum;
}MGraph;  

MGraph G;  
int P[NUM][NUM]; 
long int D[NUM]; 
int   x[9]={0};
void CreateUDN(int v,int a);
void narrate();  
void ShortestPath(int num);
void output(int sight1,int sight2);
char Menu();  
void search();  
char SearchMenu(); 
void   HaMiTonian(int);  
void   NextValue(int);   
void   display();
void main()
{
 
 int v0,v1;
 char ck;
 CreateUDN(NUM,11);
 do
 { 
  ck=Menu();
  switch(ck)
  {
  case '1':
   system("cls");
  // narrate();
   printf("\n\n\t\t\t请选择起点景点（0～8）：");
   scanf("%d",&v0);
   printf("\t\t\t请选择终点景点（0～8）：");
   scanf("%d",&v1);
   ShortestPath(v0); 
   output(v0,v1);    
   printf("\n\n\t\t\t\t请按任意键继续...\n");
   getchar();
   getchar();
   break;
  case '2':search();
   break;
  case '3':
   system("cls");
   //narrate();
   x[0]=1;  
   HaMiTonian(1);
   printf("\n\n\t\t\t\t请按任意键继续...\n");
   getchar();
   getchar();
   break;
  };
 }while(ck!='e');
 
 
}
char Menu() 
{
 char c;
 int flag;
 do{
  flag=1;
  system("cls");
  narrate();
  printf("\n\t\t\t┏━━━━━━━━━━━━━━━┑\n");
  printf("\t\t\t┃                              ┃\n");
  printf("\t\t\t┃      1、查询景点路径         ┃\n");
  printf("\t\t\t┃      2、查询景点信息         ┃\n");
  printf("\t\t\t┃      3、推荐参观路线         ┃\n");
  printf("\t\t\t┃      e、退出                 ┃\n");
  printf("\t\t\t┃                              ┃\n");
  printf("\t\t\t┗━━━━━━━━━━━━━━━┛\n");
  printf("\t\t\t\t请输入您的选择：");
  scanf("%c",&c);
  if(c=='1'||c=='2'||c=='3'||c=='e')
   flag=0;
 }while(flag);
 return c;
}

char SearchMenu() 
{
 char c;
 int flag;
 do{
  flag=1;
  system("cls");
  narrate();
  printf("\n\t\t\t┏━━━━━━━━━━━━━━━┑\n");
  printf("\t\t\t┃                              ┃\n");
  printf("\t\t\t┃      1、按照景点编号查询     ┃\n");
  printf("\t\t\t┃      2、按照景点名称查询     ┃\n");
  printf("\t\t\t┃      e、返回                 ┃\n");
  printf("\t\t\t┃                              ┃\n");
  printf("\t\t\t┗━━━━━━━━━━━━━━━┛\n");
  printf("\t\t\t\t请输入您的选择：");
  scanf("%c",&c);
  if(c=='1'||c=='2'||c=='e')
   flag=0;
 }while(flag);
 return c;
}
void search() 
{
 int num;
 int i;
 char c;
 char name[20];
 
 do
 {
  system("cls");
  c=SearchMenu();
  switch (c)
  {
  case '1': 
   system("cls");
   narrate();
   printf("\n\n\t\t请输入您要查找的景点编号：");
   scanf("%d",&num);
   for(i=0;i<NUM;i++)
   {
    if(num==G.vex[i].number)
    {
     printf("\n\n\t\t\t您要查找景点信息如下:");
     printf("\n\n\t\t\t%-25s\n\n",G.vex[i].description);
     printf("\n\t\t\t按任意键返回...");
     getchar();
     getchar();
     break;
    }
   }
   if(i==NUM)
   {
    printf("\n\n\t\t\t没有找到！");
    printf("\n\n\t\t\t按任意键返回...");
    getchar();
    getchar();
   }
  
   break;
  case '2':
   narrate();
   system("cls");
   printf("\n\n\t\t请输入您要查找的景点名称：");
   scanf("%s",name);
   for(i=0;i<NUM;i++)
   {
    if(!strcmp(name,G.vex[i].sight))
    {
     printf("\n\n\t\t\t您要查找景点信息如下:");
     printf("\n\n\t\t\t%-25s\n\n",G.vex[i].description);
     printf("\n\t\t\t按任意键返回...");
     getchar();
     getchar();
     break;
    }
   }
   if(i==NUM)
   {
    printf("\n\n\t\t\t没有找到！");
    printf("\n\n\t\t\t按任意键返回...");
    getchar();
    getchar();
   }
   break;
  }
 }while(c!='e');
}
void CreateUDN(int v,int a)
{
 int i,j;
 G.vexnum=v; 
 G.arcnum=a;
 for(i=0;i<G.vexnum;++i) G.vex[i].number=i;
 
 
 
 G.vex[0].sight="行政楼";
 G.vex[0].description="学校领导，办公室之地。";
 G.vex[1].sight="大礼堂";
 G.vex[1].description="业余活动，举办各种晚会。";
 G.vex[2].sight="11教";
 G.vex[2].description="教室，自习室";
 G.vex[3].sight="10教";
 G.vex[3].description="教室，自习室";
 G.vex[4].sight="图书馆";
 G.vex[4].description="阅览，借阅图书";
 G.vex[5].sight="第八食堂";
 G.vex[5].description="餐饮休闲";
 G.vex[6].sight="小河";
 G.vex[6].description="休闲，放松心情";
 G.vex[7].sight="第九食堂";
 G.vex[7].description="餐饮休闲";
 G.vex[8].sight="学23";
 G.vex[8].description="休息";
 
 
  for(i=0;i<G.vexnum;++i)
  for(j=0;j<G.vexnum;++j)
  G.arcs[i][j].adj=Max;
  G.arcs[0][1].adj=G.arcs[1][0].adj=12;
  G.arcs[0][2].adj=G.arcs[2][0].adj=6;
  G.arcs[0][3].adj=G.arcs[3][0].adj=5;
  G.arcs[1][4].adj=G.arcs[4][1].adj=11;
  G.arcs[2][4].adj=G.arcs[4][2].adj=2;
  G.arcs[3][5].adj=G.arcs[5][3].adj=4;
  G.arcs[5][7].adj=G.arcs[7][5].adj=9;
  G.arcs[4][6].adj=G.arcs[6][4].adj=2;
  G.arcs[4][7].adj=G.arcs[7][4].adj=14;
  G.arcs[6][8].adj=G.arcs[8][6].adj=7;
  G.arcs[7][8].adj=G.arcs[8][7].adj=3;
}
void narrate()
{
 int i,k=0;
 printf("\n\t\t*****************欢迎使用校园导游程序***************\n");
 printf("\n\t\t********************济南大学*******************\n");
 printf("\t__________________________________________________________________\n");
 printf("\t\t景点名称\t\t|\t景点描述\n");
 printf("\t________________________________|_________________________________\n");
 for(i=0;i<NUM;i++)
 {
  printf("\t (%2d)%-10s\t\t\t|\t%-25s\n",i,G.vex[i].sight,G.vex[i].description);
  k=k+1;
 }
 printf("\t________________________________|_________________________________\n");
}
void ShortestPath(int num)
{
 int v,w,i,t; 
 int final[NUM];
 int min;
 for(v=0;v<NUM;v++)
 {
  final[v]=0; 
  D[v]=G.arcs[num][v].adj;
  for(w=0;w<NUM;w++)
   P[v][w]=0;
  if(D[v]<20000) 
  {
   P[v][num]=1;
   P[v][v]=1;
  }
 }
 
 D[num]=0;
 final[num]=1;     
       
 for(i=0;i<NUM;++i)    
 {
  min=Max;    
  for(w=0;w<NUM;++w)
   if(!final[w])   
    if(D[w]<min)  
    {
     v=w;
     min=D[w];
    }
    final[v]=1;  
    for(w=0;w<NUM;++w) 
     if(!final[w]&&((min+G.arcs[v][w].adj)<D[w]))
     {
      D[w]=min+G.arcs[v][w].adj;
      for(t=0;t<NUM;t++)
       P[w][t]=P[v][t];
      P[w][w]=1;
     }
 }
}
void output(int sight1,int sight2)   
{
 int a,b,c,d,q=0;
 a=sight2;   
 if(a!=sight1)   
 {
  printf("\n\t从%s到%s的最短路径是",G.vex[sight1].sight,G.vex[sight2].sight);
  printf("\t(最短距离为 %dm.)\n\n\t",D[a]); 
  printf("\t%s",G.vex[sight1].sight);  
  d=sight1;     
  for(c=0;c<NUM;++c)
  {
gate:;       
     P[a][sight1]=0;
     for(b=0;b<NUM;b++)
     {
      if(G.arcs[d][b].adj<20000&&P[a][b]) 
      {
       printf("-->%s",G.vex[b].sight); 
       q=q+1;    
       P[a][b]=0;
       d=b;    
       if(q%8==0) printf("\n");
       goto gate;
      }
     }
  }
 }
 
}
void HaMiTonian(int m)  
{
 if(m>8)   return;  
L: NextValue(m);  
   if(x[m]==0)  
    return;  
   if(m==7&&G.arcs[0][x[8]-1].adj!=20000)  
    display();  
   else  
    HaMiTonian(m+1);  
   goto   L;  
}
void NextValue(int k)  
{  
 int j;  
l:x[k]=(x[k]+1)%10;  
  if(x[k]==0)  
   return;  
  if(G.arcs[x[k-1]-1][x[k]-1].adj!=20000)  
  {  
   for(j=0;j<k;j++)  
    if(x[j]==x[k])  
     goto l;  
    return;      
  }  
  else  
   goto l;      
}  
void display()  
{  
 int i=0;
 printf("\n\n\t");
 for(i=0;i<8;i++)  
  printf("%s->",G.vex[x[i]-1].sight);  
 printf("出口");
 printf("\n");
}