/*
此題為了方便測試，已經(jīng)將所有圖相關(guān)數(shù)據(jù)存入了in.txt文件
并且對于自己輸入的希望看到的相關(guān)城市信息，直接打印出所有情況。?
*/


#include??
#include??
using?namespace?std;??
/*鄰接矩陣的類型定義*/??
#define?MAX?10000000??
#define?MAX_VERTEX_NUM?20??
typedef?struct??
{??
????string?vexs[MAX_VERTEX_NUM];//用一維數(shù)組存儲頂點(diǎn)信息??
????int?edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//用二維數(shù)組充當(dāng)矩陣，來存儲頂點(diǎn)花銷邊的信息
	int?edges2[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//用二維數(shù)組充當(dāng)矩陣，來存儲頂點(diǎn)時間邊的信息??
????int?vexnumedgenumedgenum2;//頂點(diǎn)樹和邊數(shù)??
}MGraph;??

/*構(gòu)造有向網(wǎng)的鄰接矩陣*/??
void?CreateDN_AM（MGraph?&Gint?nint?e）??
{??
????G.vexnum=n;??
????G.edgenum=e;??
??????
????int?ijk;??
????int?weight;
	cout<<“所有城市信息如下：請對應(yīng)順序輸入“<????for（i=0;i????????{
???????	cin>>G.vexs[i];????//輸入頂點(diǎn)信息?
		cout<????????}
????for（i=0;i????????for（j=0;j????????????{
????????????G.edges[i][j]=MAX;//將矩陣初始化為MAX
			G.edges2[i][j]=MAX;//將矩陣初始化為MAX?
????????????}
	//下面初始化花銷邊信息		?
????for（k=0;k????{??
????????cin>>i>>j>>weight;??
????????G.edges[i][j]=weight;?
????}????
????//下面初始化時間邊信息
????for（k=0;k????{??
????????cin>>i>>j>>weight;??
????????G.edges2[i][j]=weight;??
????}????
}??

void?ShortestPath_DJ（MGraph?&Gint?v）??
{??
????int?ijkk2minmin2;??
????int?final[MAX_VERTEX_NUM];??//該數(shù)組用來標(biāo)識頂點(diǎn)是否已確定了最短路徑，花銷??
????int?dist[MAX_VERTEX_NUM];???//dist[i]記錄頂點(diǎn)i到?v?的最短距離?
????string?path[2*MAX_VERTEX_NUM];??
????
????int?final2[MAX_VERTEX_NUM];?//該數(shù)組用來標(biāo)識頂點(diǎn)是否已確定了最短路徑，時間??
????int?dist2[MAX_VERTEX_NUM];??//dist2[i]記錄頂點(diǎn)i到?v?的最短距離?
????string?path2[2*MAX_VERTEX_NUM];
????
????int?zhongzhuan[MAX_VERTEX_NUM];//記錄中轉(zhuǎn)次數(shù)?
????string?path3[2*MAX_VERTEX_NUM];?
????
????cout<<“下面是最短時間排序：“<	for（i=0;i????{//初始化工作??
????????dist2[i]=G.edges2[v][i];//dist數(shù)組用來存儲當(dāng)前找到的v到其他各頂點(diǎn)的最短路徑??
????????if（dist2[i]????????????{
????????????	//cout<<“dist2[“<????????????	path2[i]=G.vexs[v]+“-->“+G.vexs[i];//如果v到i有邊的話，把頂點(diǎn)字符存到path字符數(shù)組中，表示路徑?
????????????}?
????????else??
????????????path2[i]=“#“;??
????????final2[i]=0;//初始化標(biāo)識數(shù)組為0??
????}??
????dist2[v]=0;??
????final2[v]=1;??//將頂點(diǎn)v加入頂點(diǎn)集合?
????for（j=1;j????{??
????????min2=MAX;??
????????for（i=0;i????????????{
????????????	//cout<<“dist2[“<????????????	if（dist2[i]????????????	{??
????????????????min2=dist2[i];??
????????????????k2=i;??
????????????	}??????????//找到dist數(shù)組中最小值的位置k??
????????????}
????????cout<????????final2[k2]=1;//設(shè)置標(biāo)志位??
????????for（i=0;i????????{//遍歷每個頂點(diǎn)i和當(dāng)前的已求出的最短路徑的頂點(diǎn)k作比較，若從源點(diǎn)經(jīng)過頂點(diǎn)k到頂點(diǎn)i的路徑，比dist[i]小，??
????????????//則更新頂點(diǎn)dist[i]??
????????????if（dist2[i]>dist2[k2]+G.edges2[k2][i]?&&?final2[i]==0）??
????????????{??
????????????????
????????????????dist2[i]=dist2[k2]+G.edges2[k2][i];
				//cout<<“dist[k2]:“<