#include<stdio.h>
#include<malloc.h>
#include<ctype.h>
#define VEXNUM 7
#define LEN 300
#define INF 256    //INF表無窮
typedef int AdjType;
struct VexType{
      char num[2];      //景點編號
	  char name[20];    //景點名稱
      char info[100];    //景點介紹
};
typedef struct GraphMatrix{
	  int vexnum;           //圖的頂點個數(shù)
	  VexType *vexs;   //頂點信息
	  AdjType **arcs; //邊信息,存放邊長
}*pGraphMatrix;
struct Edge{
	int start_vex,stop_vex;
	AdjType w;
};
typedef struct Path{
	AdjType length;
	int prevex;
}*PPath;
//****讀取介紹****
VexType *creat_infos(int n)//各結點的信息
{
    int i;
	VexType* infos=(VexType *)malloc(sizeof(VexType)*n);
	if(!infos)
		printf("分配內存失敗!");		
	FILE *fp=fopen("信息.txt","r");
    for(i=0;i<n;i++)
	   fscanf(fp,"%s%s",infos[i].num,infos[i].name);      
	fclose(fp);
	printf("\n");
	return infos;
}
void create_graph(pGraphMatrix g)//****建圖****
{
	int i,j;
	if(!g)printf("分配內存失敗!");
    FILE *fp=fopen("vexs.txt","r");
	g->vexnum=VEXNUM;
	g->vexs=creat_infos(g->vexnum);//創(chuàng)建結點信息
    
	g->arcs=(AdjType **)malloc(sizeof(AdjType*)*g->vexnum);//創(chuàng)建關系矩陣
	for(i=0;i<g->vexnum;i++)
	{
		g->arcs[i]=(AdjType *)malloc(sizeof(AdjType)*g->vexnum);
	    for(j=0;j<g->vexnum;j++)
		{
	        g->arcs[i][j]=0;
			fscanf(fp,"%d",&g->arcs[i][j]);
		}
	}putchar('\n');
    fclose(fp);
}
//****求最小生成樹****
void prim(pGraphMatrix g,Edge* mst)
{
	int i,j,min,vx,vy,s,n;
	int w,minw;char ch;
	Edge edge;

	printf("請輸入您想要的起始點（A/a，B/b，C/c，D/d，E/e，F(xiàn)/f，G/g）：");scanf("%c",&ch);	
    if(ch<=103&&ch>=97)s=ch-97;
	else if(ch<=71&&ch>=65)s=ch-65; else printf("輸入錯誤！\n");
	
	for(i=0;i<g->vexnum;i++)mst[i].w=0;
	j=0; //引入j 
	for(i=0;i<g->vexnum;i++)//初始化mst
 	    if(s==i)continue;
		else {
			n=j++;
			mst[n].start_vex=s;
            mst[n].stop_vex=i;
            mst[n].w=g->arcs[s][i];
		}

	for(i=0;i<g->vexnum-1;i++)//求n-1條邊
	{
		minw=INF;min=i;
		for(j=i;j<g->vexnum-1;j++)
			if(mst[j].w<minw)//從（vx,vy）(vx在U中，vy在V-U中)中選出最短的邊
			{
				minw=mst[j].w;  min=j;
			}
			edge=mst[min];  mst[min]=mst[i];  mst[i]=edge;//第i條邊與最短的邊交換,把小的值往前移
			vx=mst[i].stop_vex;//加入新結點vx

			for(j=i+1;j<g->vexnum-1;j++)
				//調整mst[i+1]到mst[n-1]，看以新所向所向插入的結點為中點的路徑長度是否比原來的短
			{
				vy=mst[j].stop_vex;  w=g->arcs[vx][vy];
				if(w<mst[j].w) { mst[j].w=w; mst[j].start_vex=vx; }//start_vex指直接的起點
			}
	}
}
//****求最短路徑****
void dijkstra(pGraphMatrix g,PPath dist,int s)//S也是從0開始
{
	int i,j,min;
	AdjType minw;
    
	dist[s].length=0;dist[s].prevex=s;g->arcs[s][s]=1;//以輸入的點為起點已經(jīng)在集合U中

	for(i=0;i<g->vexnum;i++)//初始化V-U集合中頂點的距離值
	{
		if(i==s)continue;
		else{
		dist[i].length=g->arcs[s][i];
		if(dist[i].length!=INF)dist[i].prevex=s;
		else dist[i].prevex=-1; 
		}
	}

	for(i=0;i<g->vexnum;i++)//????
	{
		minw=INF;min=s;

		for(j=0;j<g->vexnum;j++)
			if(g->arcs[j][j]==0 && dist[j].length<minw)//選出距離值最小的頂點 
			{ minw=dist[j].length; min=j; }
			if(min==s)break;//從VS沒有路徑到V-U中的頂點
			g->arcs[min][min]=1;//集合V-U中路徑最小的頂點為MIN，用1標記其已選入

			for(j=0;j<g->vexnum;j++)//調整集合V-U中頂點的最短路徑
			{
				if(g->arcs[j][j]==1)continue;
				if(dist[j].length>dist[min].length+g->arcs[min][j])
				{
					dist[j].length=dist[min].length+g->arcs[min][j];//以加入的點為中點
					dist[j].prevex=min;
				}
			}
	}
}
//****輸出****
void ouput_mst(pGraphMatrix g,Edge* mst,int n)//輸出最短周游路徑  
{
	int i; char c1,c2;
	printf("\n從指定點為起點的最佳周游方案如下：\n");
	for(i=0;i<n-1;i++)
	{
		c1=65+mst[i].start_vex;c2=mst[i].stop_vex+65;
       printf("\n %c(%s)-->%c(%s)路程為：%d00米\n",c1,g->vexs[mst[i].start_vex].name,c2,g->vexs[mst[i].stop_vex].name,mst[i].w);
	 }
}
void ouput_dist(pGraphMatrix g,PPath dist)//輸出任兩點間的最短路徑 printf("fugsfduhg");
{
	int i,s,e,num=0,path[7];//S表起點下標，E表終點下標
    char ch1,ch2;

	printf("\n請輸入您想要的起始點（A/a，B/b，C/c，D/d，E/e，F(xiàn)/f，G/g）：\n");scanf("%c",&ch1);//輸入起點
	scanf("%c",&ch2);
    printf("請輸入您想要到的景點（A/a，B/b，C/c，D/d，E/e，F(xiàn)/f，G/g）：\n");scanf("%c",&ch2);//輸入終點
    if(ch1<=103&&ch1>=97)s=ch1-97;
	else if(ch1<=71&&ch1>=65)s=ch1-65; 
	else printf("輸入錯誤！\n"); e=s+ch2-ch1;

    dijkstra(g,dist,s);
    //****輸出路徑****
	if(dist[e].length>=256)printf("無法到達目的地！");
	else {printf("從 %s(%s)到 %s(%s)的最短路程為：%d00米，具體路徑如下：\n\n",
		g->vexs[s].num,g->vexs[s].name,g->vexs[e].num,g->vexs[e].name,dist[e].length);
	
	for(i=0;i<g->vexnum;i++)//得到路徑的逆序
		path[i]=-1;
	for(i=g->vexnum-1;i>=0&&e!=dist[e].prevex;i--)
	{
		path[i]=e;
		e=dist[e].prevex;
	}   path[i]=s;

  for(i=0;i<g->vexnum-1;i++)
	{
	   if(path[i]==-1)continue;
		  else{ ch1=path[i]+65;
		   printf("%c (%s)--> ",ch1,g->vexs[path[i]].name);
		  }
		  num++;if(num%4==0)putchar('\n');
	}
	   ch1=path[i]+65;
    printf("%c (%s)",ch1,g->vexs[path[i]].name);
	putchar('\n');
	}
}
void output_info(pGraphMatrix g)
{
	char a; int b;
printf("\nA、大禮堂 B、綜合樓 C、圖書館 D、博物館 E、課室 F、工科樓 G、辦公樓 H、返回 \n\n您想了解的景點是：\n");
getchar();     
	while(1)
	{scanf("%c",&a);toupper(a);if(a=='h'||a=='H')return;//break
	printf("\n1、英文版2、中文版 請選擇：\n");
	scanf("%d",&b);
		switch(b)
	{
		case 1:
		switch(a)
		{
		case'a':
		case'A':printf("How grand the building is.It looks so glorious in the sunshine.It is round seen from the sky.This building has three storeys.It's used for holding important meeting or celebrating important  activities.The groundfloor has a room for students learning arts.\n");break;
		case'b':
		case'B':printf("It is on the opposite side of Assembly_hal.It has five storeys.Naturally,you can see from name that it's used for all kinds of scourses.So you can go there to enjoy atmosphere of different fields of sciences,such as ChineseMedicine,Computering and so on.\n");break;
		case'c':
		case'C':printf("Look,there is an old man with the dressing of HangDynasty.Oh no,it's not a real man,it's just a sculpture.It is ZhangZhongjin,a famous Chinese doctor who wrote the book 'Shang Han Lun'.Behind it is our library,which has five floors.Thouands of books are stored there.Every day many students go here to absorb knowledge.\n");break;
		case'd':
		case'D':printf("Oh,it's the building with so many strange things.It also displays many medals won by our students and teachers.Many kinds of important creature series are kept here,including herbal medicine.\n");break;
		case'e':
		case'E':printf("The office building is administration of the college.There are 13 floors and every floor belongs to different departerment.Many important things are disposed in the building.\n");break;
		case'f':
		case'F':printf("The teaching building is very important for students.Mostly all students take classes here. The building consists of District A .\n");break;
		case'g':
		case'G':printf("The engineering building is the network center of the college. \n");break;
		};break;
		case 2:
        switch(a)
		{
		case'a':
		case'A':printf("大禮堂是一座雄偉的圓形建筑.這個建筑有三層,通常用來舉行一些重大的會議或者慶祝活動.底層有一個寬敞的大廳可以供一些學生練習音樂舞蹈什么的.\n");break;
		case'b':
		case'B':printf("綜合樓在禮堂對面,它有五層樓.從它的名字你可以很自然的知道在這棟樓開設了各種各樣的課程,你可以在其中感受到各種不同學科的氛圍.\n");break;
		case'c':
		case'C':printf("圖書館前面的雕像是漢代的名醫(yī)張仲景,他寫的<<傷寒論>>是經(jīng)典醫(yī)學名篇.圖書館有五層,藏書豐富,但多為醫(yī)藥類書籍.\n");break;
		case'd':
		case'D':printf("博物館,也許名不副實.當然,我們太少去參觀了.據(jù)說陳列了許多藥材,有名貴的,稀奇古怪的,也有常規(guī)藥材.\n");break;
		case'e':
		case'E':printf("辦公樓學校的行政部門所在地,它有13層樓,每一層都分屬不同的部門.學校諸多重大的事情都是在這里處理的.\n");break;
		case'f':
		case'F':printf("教學樓是學生上課的重要場所,分A、B區(qū)。\n");break;
		case'g':
		case'G':printf("工科樓是學校的網(wǎng)絡中心。\n");break;
		}
		}printf("\nA、大禮堂  B、綜合樓  C、圖書館  D、博物館  E、課室  F、工科樓  G、辦公樓H、返回 \n您想了解的景點是：\n");
     scanf("%c",&a);toupper(a);
	}
}
void main()
{
	int i;
	pGraphMatrix g;    g=(pGraphMatrix)malloc(sizeof(GraphMatrix));//初始化
	PPath dist;     dist=(PPath)malloc(sizeof(Path));
	Edge* mst;    mst=(Edge*)malloc(sizeof(Edge));
    
    create_graph(g);
    printf("\n****************************歡迎進入廣中醫(yī)校園導航系統(tǒng)**************************\n\n");
    while(1)
	{
		printf("\t請選擇：\n\n\t1、各景點信息查尋\t        2、總游覽路線(最短路徑)\t\n\n\t3、游覽某一景點的最短路徑\t0、退出\n");
		scanf("%d",&i); if(i==0){
			printf("\n******************************謝謝！歡迎再次使用！******************************\n");break;}
	switch(i)
	{
	case 1:output_info(g);break;
	case 2:prim(g,mst);ouput_mst(g,mst,g->vexnum);break;
	case 3:ouput_dist(g,dist);break;
	}		
	}
}