#include<iostream.h>

// 定義 狀態(tài)代碼 及 數(shù)據(jù)類型
#define NULL 0
#define OK 1
#define ERROR 0
#define INFINITY 255
#define MAX_VERTEX_NUM 20

typedef int Status;
typedef int ElemType;

// -----------------------  隊(duì)列結(jié)構(gòu)  -------------------------

// 節(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)
typedef struct QNode{
	ElemType data;
	struct QNode *next;
}QNode,*QueuePtr;


// 隊(duì)列
typedef struct{
	QueuePtr front;
	QueuePtr rear;
}LinkQueue;

// 初始化隊(duì)列
Status InitQueue(LinkQueue &Q){
	Q.front=Q.rear=new QNode;
	if(!Q.front) 
		return ERROR;
	Q.front->next=NULL;
	return OK;
}

// 入隊(duì)
Status EnQueue(LinkQueue &Q,ElemType e){
	QueuePtr p=NULL;
	p=new QNode;
	if(!p)
		return ERROR;
	p->data=e;
	p->next=NULL;
	Q.rear->next=p;
	Q.rear=p;
	return OK;
}

// 出隊(duì)
Status DeQueue(LinkQueue &Q,ElemType &e){
	QueuePtr p=NULL;
	if(Q.front==Q.rear)
		return ERROR;
	p=Q.front->next;
	e=p->data;
	Q.front->next=p->next;
	if(Q.rear==p)			// 注意當(dāng)出隊(duì)后為空隊(duì)的情況
		Q.rear=Q.front;
	delete p;
	return OK;
}

// 判斷是否為空隊(duì)列
Status EmptyQueue(LinkQueue &Q){
	return Q.front==Q.rear?true:false;
}

// 復(fù)制隊(duì)列(copy Q1 to Q2)
Status CopyQueue(LinkQueue &Q1,LinkQueue &Q2){
	int e;
	QueuePtr p;
	while(!EmptyQueue(Q2)){		// clean Q2
		DeQueue(Q2,e);
	}							// copy one by one
	p=Q1.front->next;
	while(p){
		e=p->data;
		p=p->next;
		EnQueue(Q2,e);
	}
	return OK;
}

// ----------------------  圖的結(jié)構(gòu)：鄰接矩陣（有向網(wǎng)）  --------------------------//

// 鄰接矩陣元素
typedef struct ArcCell{
	int adj;			// arc value: >0, INFINITY: no link
	char *info;			
}AcrCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

// 圖的結(jié)構(gòu)	
typedef struct{
	char vexs[MAX_VERTEX_NUM][5];		// 頂點(diǎn)數(shù)組
	AdjMatrix arcs;					// 鄰接矩陣
	int vexnum;						// 圖當(dāng)前的頂點(diǎn)數(shù)
	int arcnum;						// 圖當(dāng)前邊的個(gè)數(shù)
}MGraph;

// 建立鄰接圖（key=1為有向網(wǎng)，key=0為無(wú)向網(wǎng)）
Status CreateUDN(MGraph &G,int vexnum,int edgenum,char *names,char *edges,int key){
	int i,j,k,value;
	// 輸入當(dāng)前圖的頂點(diǎn)數(shù)，邊個(gè)數(shù)
	G.vexnum=vexnum;
	G.arcnum=edgenum;
	// 各個(gè)頂點(diǎn)數(shù)據(jù)
	for(i=0;i<G.vexnum;++i){
		for(j=0;j<4;j++){
			G.vexs[i][j]=*names;
			names++;
		}
		G.vexs[i][4]='\0';
	}
	// 初始化鄰接矩陣（全為INFINITY）
	for(i=0;i<MAX_VERTEX_NUM;++i){
		for(j=0;j<MAX_VERTEX_NUM;++j){
			G.arcs[i][j].adj=INFINITY;
			G.arcs[i][j].info=NULL;
			
		}
	}
	// 建立鄰接矩陣每條邊的數(shù)值
	for(k=0;k<G.arcnum;++k){
		i=int(*edges)-48;
		edges++;
		j=int(*edges)-48;
		edges++;
		value=(int(*edges)-48)*10;
		edges++;
		value+=int(*edges)-48;
		edges++;
		G.arcs[i][j].adj=value;
		if(!key){
			G.arcs[j][i].adj=value;
		}
	}
	return OK;
}

// 打印出鄰接矩陣
void PrintGraph(MGraph &G){
	int i,j;
	cout<<"\n//--------------- PrintMatrix -----------------//\n\n      ";
	for(i=0;i<G.vexnum;++i){
		cout<<G.vexs[i]<<"   ";
	}
	cout<<endl;
	for(i=0;i<G.vexnum;++i){
		cout<<"\n\n"<<G.vexs[i]<<"   ";
		for(j=0;j<G.vexnum;++j){
			if(G.arcs[i][j].adj==INFINITY)
				cout<<"  /    ";
			else
				cout<<" "<<G.arcs[i][j].adj<<"    ";
		}
	}
	cout<<"\n\n//--------------- PrintMatrix -----------------//\n";
}


// ----------------------  求源點(diǎn)v0到各點(diǎn)的最短路徑  --------------------------//

void ShortestPath(MGraph &G,int v0){
	int D[MAX_VERTEX_NUM],final[MAX_VERTEX_NUM],i,w,v=0,min;
	// 建立隊(duì)列數(shù)組，用以依次儲(chǔ)存最短的路徑
	LinkQueue Q[MAX_VERTEX_NUM];
	// 初始化數(shù)組
	for(i=0;i<G.vexnum;++i){
		InitQueue(Q[i]);
		D[i]=G.arcs[v0][i].adj;
		final[i]=false;
	}
	final[v0]=true;
	// 一個(gè)一個(gè)循環(huán)找出最短距離（共vexnum－1個(gè)）
	for(i=1;i<G.vexnum;++i){
		min=INFINITY;
		// 掃描找出非final集中最小的D[]
		for(w=0;w<G.vexnum;++w){
			if(!final[w] && D[w]<min){
				v=w;
				min=D[w];
			}
		}
		final[v]=true;
		// 更新各D[]數(shù)據(jù)
		for(w=0;w<G.vexnum;++w){
			if(!final[w] && G.arcs[v][w].adj+min<D[w]){
				D[w]=G.arcs[v][w].adj+min;
				CopyQueue(Q[v],Q[w]);
				EnQueue(Q[w],v);
			}
		}
	}
	// 打印出結(jié)果
	cout<<"//--------------- ShortestPath -----------------//\n\n";
	cout<<"  出發(fā)地->目的地\t最短距離\t詳細(xì)路徑\n\n";
	for(i=0;i<G.vexnum;i++){
		if(D[i]!=INFINITY){
			cout<<"  "<<G.vexs[v0]<<" -> "<<G.vexs[i]<<"\t\t"<<D[i]<<"   \t\t";
			cout<<G.vexs[v0];
			while(!EmptyQueue(Q[i])){
				DeQueue(Q[i],v);
				cout<<" -> "<<G.vexs[v];
			}
			cout<<" -> "<<G.vexs[i]<<endl;
		}else{
			cout<<"  "<<G.vexs[v0]<<" -> "<<G.vexs[i]<<"\t\tNo path!\n";
			
		}
	}
	cout<<"\n//--------------- ShortestPath -----------------//\n";
}

void PrintCity(char *names,int vexnum){
	int i,j;
	cout<<"城市列表：\n\n";
	for(i=0;i<vexnum;++i){
		cout<<" "<<i<<"-";
		for(j=0;j<4;j++){
			cout<<*names;
			names++;
		}
		cout<<" ";
	}
	cout<<"\n請(qǐng)選擇出發(fā)城市 >";
}



void main(){
	MGraph G;

	// 圖的結(jié)構(gòu)數(shù)據(jù)
	char *edges,*names;
	int vexnum,arcnum,city,kind;
	vexnum=10;
	arcnum=14;
	names="鄭州北京天津南昌上海貴陽(yáng)株洲廣州蘭州西寧";
	edges="01450235035012201591187024503450585056205750604063409835";

	
	do{
		PrintCity(names,vexnum);
		cin>>city;
		cout<<"\n\n操作：\n0－無(wú)向圖列表 1－有向圖列表\n2－無(wú)向圖矩陣  3－有向圖矩陣\n4－選擇城市 5－退出\n\n請(qǐng)選擇操作 >";
		do{
			cin>>kind;
			if(kind>=0 && kind <=3){
				CreateUDN(G,vexnum,arcnum,names,edges,kind%2);
				switch(kind/2){
				case 0:ShortestPath(G,city);
					break;
				case 1:PrintGraph(G);
					break;
				}
			}
			cout<<"\n\n操作：\n0－無(wú)向圖列表 1－有向圖列表\n2－無(wú)向圖矩陣  3－有向圖矩陣\n4－選擇城市 5－退出\n\n請(qǐng)選擇操作 >";
		}
		while(kind<4);
	}
	while(kind<5);
}