/*校園導遊計劃*/*[問題描述]
用無向網絡表示學校的校園景點平面圖，地圖中的頂點表示主要景點。
存儲景點編號、名稱、介紹等信息。圖中的邊表示景點之間的道路，存儲路徑長度等信息。要求能夠回答關於景點介紹，遊覽路線等問題。
遊客可以通過終端詢問:
(1)從壹個景點到另壹個景點的最短路徑。
(2)遊客入園，選擇最佳路線。
(3)遊客可以不重復瀏覽景點，最後返回出口(出口在入口旁邊)。
[基本要求]
(1)導遊圖被視為壹個加權的無向圖，頂點代表公園內的景點，邊代表景點之間的道路。
邊緣的重量表示距離。為該圖選擇適當的數據結構。
(2)向遊客展示各種路徑，遊客可以自行選擇瀏覽路線。
(3)在屏幕上畫出景點分布圖。
[實施提示]
(1)構造壹個無向圖G，用鄰接矩陣存儲。
(2)利用Dijstra算法計算從起點到每個頂點的最短路徑，並用二維數組p[i][]記錄。
最短路徑長度由壹維數組d[i]存儲；I的取值範圍:0 ~ 20。
(3)壹維數組have[]用於記錄最短路徑出現的順序。
(4)根據起點和終點輸出最短路徑和路徑長度。
*/
#定義INFINITY 10000/* INFINITY */
#定義最大頂點數40
#定義最大40
# include & ltstdlib.h & gt
# include & ltstdio.h & gt
# include & ltconio.h & gt
# include & ltstring.h & gt
typedef結構ArCell
{
int adj//路徑長度
}ArCell，adj matrix[最大頂點數][最大頂點數]；
圖中的Typedef struct // Vertex表示主要景點，存儲了景點的編號、名稱、介紹等信息。
{
char name[30]；
int num
char簡介[100]；//簡介
}信息類型；
typedef結構
{
infotype vexs[MAX _ VERTEX _ NUM]；
鄰接矩陣弧；
int vexnum，arcnum
} MGraph
m圖表b；
void cmd(無效)；
MGraph InitGraph(void)；
void菜單(void)；
void瀏覽器(m graph * G)；
void shortest path _ DIJ(m graph * G)；
void Floyd(m graph * G)；
void搜索(m graph * G)；
int LocateVex(MGraph *G，char * v)；
m graph * CreatUDN(m graph * G)；
void print(m graph * G)；
/******************************************************/
無效總管(無效)
{
system(" color 1f ")；
system(" mode con:cols = 140 lines = 130 ")；
cmd()；
}
/******************************************************/
無效命令
{
int I；
b = init graph()；
menu()；
scanf("%d "，& ampI)；
而(我！=5)
{
開關(壹)
{
案例1:系統(" cls ")；瀏覽器(& ampb)；menu()；打破；
案例二:系統(“cls”)；DIJ最短路徑(& ampb)；menu()；打破；
案例三:系統(“cls”)；弗洛伊德(& ampb)；menu()；打破；
案例四:系統(“cls”)；搜索(ampb)；menu()；打破；
案例五:出口(1)；打破；
默認:break
}
scanf("%d "，& ampI)；
}
}
初始圖(無效)
{
m graph G；
int i，j；
g . vex num = 10；
g . arcnum = 14；
for(I = 0；我& ltg .維克斯努姆；i++)
維克斯[我]。num = I；
Strcpy(G.vexs[0])。名稱，“綜合食堂”)；
Strcpy(G.vexs[0])。簡介，“新標準化食堂”)；
Strcpy(G.vexs[1])。名稱，“東西辦公樓”)；
Strcpy (G. VEXS [1])。介紹，“全體教師辦公用房，12層，設施齊全”)；
Strcpy (g.vexs [2].姓名，“5號學生宿舍”)；
Strcpy(G.vexs[2].簡介，“計算機系男生宿舍，蘇式建築”)；
Strcpy(G.vexs[3])。姓名，“醫院”)；
Strcpy(G.vexs[3])。介紹，“校醫院，設施不是很齊全，只能看小病，收費比較貴”)；
Strcpy(G.vexs[4])。名，“庫”)；
Strcpy(G.vexs[4])。介紹，“有60萬冊書，設施不錯，二樓是電子閱覽室，環境優雅”)；
Strcpy(G.vexs[5])。名字，“足球場”)；
Strcpy(G.vexs[5])。介紹，“現代塑膠跑道，人造草坪，適合鍛煉身體的地方”)；
Strcpy(G.vexs[6])。名，“沁園”)；
Strcpy(G.vexs[6])。簡介，“綠樹成蔭，適合休息閱讀”)；
Strcpy(G.vexs[7])。名稱，“主教學樓”)；
Strcpy(G.vexs[7])。介紹，“學院最大的教學樓，有***5層，圓形建築，適合學習”)；
Strcpy(G.vexs[8])。名，“西教學樓”)；
Strcpy(G.vexs[8])。簡介，“我院第二大教學樓，環境差”)；
Strcpy(G.vexs[9])。名稱，“多媒體大樓”)；
Strcpy(G.vexs[9])。簡介，“設施先進、環境良好的多媒體教學場所”)；
for(I = 0；我& ltg .維克斯努姆；i++)
for(j = 0；j & ltg .維克斯努姆；j++)
G.arcs[i][j]。adj =無窮大；
G.arcs[0][1]。adj = 100；
G.arcs[0][2]。adj = 200
G.arcs[0][6]。adj = 400
G.arcs[1][7]。adj = 300
G.arcs[2][3]。adj = 120；
G.arcs[3][6]。adj = 220
G.arcs[3][4]。adj = 100；
G.arcs[4][5]。adj = 300
G.arcs[4][9]。adj = 250
G.arcs[5][9]。adj = 350
G.arcs[6][7]。adj = 60
G.arcs[6][9]。adj = 200
G.arcs[7][8]。adj = 50
G.arcs[8][9]。adj = 20
for(I = 0；我& ltg .維克斯努姆；i++)
for(j = 0；j & ltg .維克斯努姆；j++)
電弧[j][i]。adj=G.arcs[i][j]。adj
返回G；
}//初始化圖形結束
無效菜單()
{
Printf("\n石家莊鐵道學院導遊圖\ n ")；
printf(“┏━━━━━━━━━━━━━━━━━━━━┓\n”)；
Printf(" ┃ 1。瀏覽校園全景┃\n》)；
printf(《┃2。查看┃\n所有旅遊線路”)；
printf(《┃3。選擇起點和目的地┃\n”)；
printf(“┃4。查看景區信息┃\n”)；
printf(“┃5。退出系統┃\n”)；
printf(“┗━━━━━━━━━━━━━━━━━━━━┛\n”)；
printf(" Option-:")；
}
無效瀏覽器(MGraph *G)
{
int v；
printf("┏━━┳━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n”)；
Printf("┃號┃景點名稱┃介紹┃\n》)；
for(v = 0；v & ltg-& gt；vexnumv++)
printf("┃%-4d┃%-16s┃%-56s┃\n",g->；煩惱。num，G->煩惱。名稱，G-& gt；煩惱。簡介)；
printf("┗━━┻━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n”)；
}
//Dijkstra算法計算起點到每個頂點的最短路徑，以v0為起點。
void最短路徑_DIJ(MGraph * G)
{
int v，w，I，min，t=0，x，flag=1，v 0；
int final[20]，D[20]，p[20][20]；
while(標誌)
{
Printf("請輸入壹個起始景點號:")；
scanf("%d "，& ampv 0)；
if(v 0 & lt；0 | | v0 & gtg-& gt；vexnum)
{
Printf("景點號不存在！請重新輸入景點編號:“)；
scanf("%d "，& ampv 0)；
}
if(v 0 & gt；= 0 & amp& ampv0 & ltg-& gt；vexnum)
flag = 0；
}
for(v = 0；v & ltg-& gt；vexnumv++)
{
final[v]= 0；
d[v]= G-& gt；arcs[v0][v]。adj
for(w = 0；w & ltg-& gt；vexnumw++)
p[v][w]= 0；
if(D[v]& lt；無窮大)
{
p[v][v 0]= 1；p[v][v]= 1；
}
}
d[v 0]= 0；final[v 0]= 1；
for(I = 1；我& ltg-& gt；vexnumi++)
{
min =無窮大；
for(w = 0；w & ltg-& gt；vexnumw++)
如果(！最終[w])
if(D[w]& lt；min){ v = w；min = D[w]；}
final[v]= 1；
for(w = 0；w & ltg-& gt；vexnumw++)
如果(！最終[w]& amp；& amp(min+G-& gt；弧線[v][w]。adj & ltD[w])
{
D[w]=min+G->弧線[v][w]。adj
for(x = 0；x & ltg-& gt；vexnumx++)
p[w][x]= p[v][x]；
p[w][w]= 1；
}
}
for(v = 0；v & ltg-& gt；vexnumv++)
{
如果(v0！=v) printf("%s "，G-& gt；vexs[v0]。姓名)；
for(w = 0；w & ltg-& gt；vexnumw++)
{
if(p[v][w]& amp；& ampw！= v 0)printf("-& gt；%s "，G-& gt；維克斯[w]。姓名)；
t++；
}
if(t & gt；g-& gt；維克斯納姆-1 & amp；& ampv0！=v)printf("總路線長度%dm\n\n "，D[v])；
}
}//ShortestPath_DIJ結束
虛空弗洛伊德(MGraph *G)
{
int v，u，I，w，k，j，flag=1，p[10][10][10]，D[10][10]；
for(v = 0；v & ltg-& gt；vexnumv++)
for(w = 0；w & ltg-& gt；vexnumw++)
{
D[v][w]=G->弧線[v][w]。adj
for(u = 0；u & ltg-& gt；vexnumu++)
p[v][w][u]= 0；
if(D[v][w]& lt；無窮大)
{
p[v][w][v]= 1；p[v][w][w]= 1；
}
}
for(u = 0；u & ltg-& gt；vexnumu++)
for(v = 0；v & ltg-& gt；vexnumv++)
for(w = 0；w & ltg-& gt；vexnumw++)
if(D[v][u]+D[u][w]& lt；D[v][w])
{
D[v][w]= D[v][u]+D[u][w]；
for(I = 0；我& ltg-& gt；vexnumi++)
p[v][w][I]= p[v][u][I]| | p[u][w][I]；
}
while(標誌)
{
Printf("請輸入起點和終點的編號:")；
scanf("%d%d "，& ampk & amp；j)；
if(k & lt；0 | | k & gtg-& gt；vexnum | | j & lt0 | | j & gtg-& gt；vexnum)
{
Printf("景點號不存在！請重新輸入起點和終點號碼:“)；
scanf("%d%d "，& ampk & amp；j)；
}
if(k & gt；= 0 & amp& ampk & ltg-& gt；維克斯納姆公司。& ampj & gt= 0 & amp& ampj & ltg-& gt；vexnum)
flag = 0；
}
printf("%s "，G-& gt；維克斯[k]。姓名)；
for(u = 0；u & ltg-& gt；vexnumu++)
if(p[k][j][u]& amp；& ampk！= u & amp& ampj！=u)
printf("-& gt；%s "，G-& gt；維克斯[u]。姓名)；
printf("-& gt；%s "，G-& gt；維克斯[j]。姓名)；
Printf("總路線長度%dm\n "，D[k][j])；
}//弗洛伊德結束
無效搜索(管理圖*G)
{
int k，flag = 1；
while(標誌)
{
Printf("請輸入要查詢的景點編號:")；
scanf("%d "，& ampk)；
if(k & lt；0 | | k & gtg-& gt；vexnum)
{
Printf("景點號不存在！請重新輸入景點編號:“)；
scanf("%d "，& ampk)；
}
if(k & gt；= 0 & amp& ampk & ltg-& gt；vexnum)
flag = 0；
}
printf("┏━━┳━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n”)；
Printf("┃號┃景點名稱┃介紹┃\n》)；
printf("┃%-4d┃%-16s┃%-56s┃\n",g->；維克斯[k]。num，G->維克斯[k]。名稱，G-& gt；維克斯[k]。簡介)；
printf("┗━━┻━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n”)；
}//搜索結束
int LocateVex(MGraph *G，char* v)
{
int c=-1，I；
for(I = 0；我& ltg-& gt；vexnumi++)
if(strcmp(v，G-& gt；維克斯[我]。name)==0)
{ c = I；打破；}
返回c；
}
MGraph * CreatUDN(MGraph *G)//初始化圖形並接受用戶輸入。
{
int i，j，k，w；
char v1[20]，v2[20]；
Printf("請輸入圖的頂點數和弧數:")；
scanf("%d%d "，& ampg-& gt；維克斯納姆。g-& gt；arcnum)；
Printf("請輸入景點編號、名稱及簡介:\ n ")；
for(I = 0；我& ltg-& gt；vexnumi++)
{
Printf("景點號:")；
scanf("%d "，& ampg-& gt；vexs-& gt；num)；
Printf("景點名稱:")；
scanf("%s "，G-& gt；維克斯[我]。姓名)；
Printf("景點介紹:")；
scanf("%s "，G-& gt；vexs-& gt；簡介)；
}
for(I = 0；我& ltg-& gt；vexnumi++)
for(j = 0；j & ltg-& gt；vexnumj++)
g-& gt；arcs[i][j]。adj =無窮大；
Printf("請輸入路徑長度:\ n ")；
for(k = 0；k & ltg-& gt；arcnumk++)
{
Printf ("side %d: \n "，k+1)；
Printf("景點對(x，y):")；
scanf("%s "，v 1)；
scanf("%s "，v2)；
Printf("路徑長度:")；
scanf("%d "，& ampw)；
i=LocateVex(G，v 1)；
j=LocateVex(G，v2)；
如果(i & gt= 0 & amp& ampj & gt=0)
{
g-& gt；arcs[i][j]。adj = w；
g-& gt；arcs[j][I]= G-& gt；arcs[I][j]；
}
}
返回G；
}
無效打印(管理圖*G)
{
int v，w，t = 0；
for(v = 0；v & ltg-& gt；vexnumv++)
for(w = 0；w & ltg-& gt；vexnumw++)
{ if(G-& gt；弧線[v][w]。adj = =無窮大)
printf("∞；")；
else printf("%-7d "，G-& gt；弧線[v][w]。adj)；
t++；
if(t % G-& gt；vexnum==0)
printf(" \ n ")；
}
}