// sx1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream.h>
#include <stdlib.h>
#include <iomanip.h>
#include <fstream.h>

#define MVNum 500                              //最大頂點數(shù)
#define Maxint 80000

enum boolean{FALSE,TRUE};

typedef  int   VRType;
typedef  char  InfoType;
typedef  char  VertexType;
typedef	 int   Status;
typedef  int   AdjMatrix;

int vexnum;                                     //頂點總數(shù)
int arcnum;                                     //弧（邊）總數(shù)

typedef   struct  vnode{
	AdjMatrix number;
	VertexType name[50];
	InfoType  info[100];
}vnode;                                         //將頂點定義為結(jié)構(gòu)體，查找時用number進行查找更方便

typedef struct{                                 //圖的定義
	vnode V[MVNum];                             //頂點表，用一維向量即可
	AdjMatrix arcs[MVNum][MVNum];               //鄰接矩陣                    
}Mgraph; 

void text(Mgraph *G)
{
    int i,j,k,w;
	ifstream inFile("vera.txt");
    if(!inFile)
		{ 
			cerr<<"cannot open vera.dat"<<endl;
			exit(1);
		}
    inFile>>vexnum>>arcnum;
	for(i=1;i<=9;i++)
		inFile>>G->V[i].number>>G->V[i].name>>G->V[i].info;
	for(i=1;i<=9;i++)                                           //初始化鄰接矩陣	
		for(j=1;j<=9;j++)
			G->arcs[i][j]=Maxint;
	for(k=1;k<=10;k++)
	{	
		inFile>>i>>j>>w;
		G->arcs[i][j]=G->arcs[j][i]=w;
	}
}

void print(Mgraph *G)
{
	int i;
	for(i=1;i<=9;i++)
    {
		cout<<G->V[i].number<<G->V[i].name<<endl;
	}
}

void Dijkstra(Mgraph *G,int v1, int n)
{
	//用Dijkstra算法求有向圖G的v1頂點到其他頂點v的最短路徑Path[v]及其距離Dist[v]
	//S[v]為真當(dāng)且僅當(dāng)v屬于S,即已求得從vl到v的最短路徑
	int Dist[MVNum],Path[MVNum];
	int i,w,min;
	int v,vt;
	enum boolean S[MVNum];
	for(v=1;v<=n;v++)
	{//初始化S和Dist
		S[v]=FALSE;                          //置空最短路徑終點集
		Dist[v]=G->arcs[v1][v];	             //置初始的最短路徑值
		if(Dist[v]<Maxint)  
			Path[v]=v1;                      //v1是v的前趨
		else Path[v]=0;                      //v無前趨
	}
	Dist[v1]=0;
	S[v1]=TRUE;                              //S集初始時只有源點、源點到源點的距離為0
	//開始循環(huán)、每次求得v1到某個v頂點的最短路徑，并加v到S集中
	for(i=2;i<n;i++)
	{//其余n-1個頂點
		min=Maxint;
		for(w=1;w<=n;w++)
			if(!S[w]&&Dist[w]<min) 
				{v=w;min=Dist[w];}			      //w頂點離v1頂點更近
				S[v]=TRUE;
		for(w=1;w<=n;w++)                     //更新當(dāng)前最短路徑及距離
			if(!S[w]&&(Dist[v]+G->arcs[v][w]<Dist[w]))
			{//修改Dist[w]和Path[w],w屬于V-S
				Dist[w]=Dist[v]+G->arcs[v][w];
				Path[w]=v;
			}
	}
	cout<<"請輸入要查詢的終點標(biāo)號"<<endl;
	cin>>vt;
	cout<<"路徑長度：路徑為："<<endl;
	cout<<setw(5)<<Dist[vt];
	cout<<setw(5)<<endl;
	v=Path[vt];
	while(v!=0)
	{
		cout<<"<-"<<v;
		v=Path[v];
	}
		cout<<endl;
}

void main()
{
	int n1,n2;
	int v,i,j;	
	cout<<"         ##################歡迎來到XXXX！################"<<endl<<endl;
	cout<<"########################這是一個校園景點查詢系統(tǒng)！###########################"<<endl<<endl;
	
	Mgraph *G;
	G=new Mgraph;
	ifstream inFile("vera.txt");
    if(!inFile)
		{ 
			cerr<<"cannot open vera.dat"<<endl;
			exit(1);
		}
    inFile>>n1>>n2;
	cout<<"**********XXXX共有"<<n1<<"個景點**********"<<endl<<endl;
	cout<<"**********各景點間有"<<n2<<"條路徑**********"<<endl<<endl;
	cout<<"**********以下為各標(biāo)號以及其對應(yīng)的景點**********"<<endl<<endl;
	text(G);
	print(G);
	do
	{
		cout<<"要進行景點信息查詢，請輸入1"<<endl;
		cout<<"要進行景點之間路徑查詢，請輸入2"<<endl;
		cout<<"要退出本系統(tǒng)，請輸入0"<<endl<<endl;
		cin>>i;
		switch(i)
		{
		case 1:
			cout<<"請輸入您要查詢的景點的標(biāo)號"<<endl;
			cin>>j;
			cout<<G->V[j].name<<G->V[i].info<<endl;
			break;
		case 2:
			cout<<"請輸入要查詢的源景點的標(biāo)號v：";
			cin>>v;
			Dijkstra(G,v,n1);                         //調(diào)用迪杰斯特拉算法
			cout<<"最短路徑已得出！"<<endl;
			break;
		case 0: 
			exit(0);
		}
	}while(i!=0);
}