#include<stdio.h>
#include<stdlib.h>
#define INT_MAX 10000
#define n 10 //定义结点值
int cost[n][n]; //权值
int shortest[n][n]; //两点间的最短距离
int path[n][n]; //经过的景点路径
void introduce(); //景点介绍函数
int shortestdistance();
void floyed(); //最短路径查询函数
void display(int i,int j); //输出最短路径结果函数
void view() //景点信息
{
printf("*----------------欢迎使用湖北师范学院导游咨询系统!----------------*\n\n");
printf("学校景点列表:\n");
printf("1:湖师大门 ");
printf("2:科教大厦 ");
printf("3:图书馆 ");
printf("4:综合楼 ");
printf("5:体育馆 \n");
printf("6:运动场 ");
printf("7:学生宿舍 ");
printf("8:莲花剧院 ");
printf("9:青山湖 ");
printf("10:文外学院 \n\n");
printf("湖北师范学院的路径图:\n");
printf(" 600 500 \n");
printf(" 科教大厦*2 莲花剧院*8 --------*9--------*10文外学院 \n");
printf(" / \\ / \\ 青山湖 \n");
printf(" / \\ / \\ \n");
printf(" 200 / \\500 / 900 \\ 400 \n");
printf(" / \\ / \\ \n");
printf(" / \\ / 500 \\ \n");
printf("湖师大门 1* 综合楼 *4-------------*7 学生宿舍 \n");
printf(" \\ / | | \n");
printf(" \\ 300 / | | \n");
printf(" 300\\ / | | \n");
printf(" \\ / |200 |300 \n");
printf(" 图书馆 *3 | | \n");
printf(" | 400 | \n");
printf(" 体育馆 *5-------------*6 运动场 \n");
printf(" \n");
}
void main() //主函数
{
int i,j,a;
view();
for(i=0;i<=n;i++)
for(j=0;j<=n;j++) cost[i][j]=INT_MAX;
cost[1][2]=cost[2][1]=200; //权值，即距离
cost[1][3]=cost[3][1]=300;
cost[2][4]=cost[4][2]=500;
cost[3][4]=cost[4][3]=300;
cost[4][5]=cost[5][4]=200;
cost[4][7]=cost[7][4]=500;
cost[4][8]=cost[8][4]=900;
cost[5][6]=cost[6][5]=400;
cost[6][7]=cost[7][6]=300;
cost[7][8]=cost[8][7]=400;
cost[8][9]=cost[9][8]=600;
cost[9][10]=cost[10][9]=500;
cost[1][1]=cost[2][2]=cost[3][3]=cost[4][4]=cost[5][5]=0;
cost[6][6]=cost[7][7]=cost[8][8]=cost[9][9]=cost[10][10]=0;
while(1)
{
printf("请选择您需要的服务：\n");
printf("1.景点信息查询………请按 1 键\n");
printf("2.景点最短路径查询…请按 2 键\n");
printf("3.退出系统……………请按 3 键\n");
printf("请选择服务:");
scanf("\n%d",&a);
switch(a)
{
case 1:
printf("进入景点信息查询:");
introduce();
break;
case 2:
printf("进入最短路径查询:");
shortestdistance();
break;
case 3:
exit(0);
default:
printf("输入信息错误！\n请输入数字1或2或3.\n");
break;
}
}
}
void introduce() /*景点信息查询*/
{
int a;
printf("您想查询哪个景点的详细信息?请输入景点编号:");
scanf("%d",&a);
printf("\n");
switch(a)
{
case 1:
printf("1:学校大门\n\n 湖北师范学院正门，左右科教大厦和信息大厦相对而立，气势恢宏。\n\n");break;
case 2:
printf("2:科教大厦\n\n 学校领导的办公大楼，同时也是主要教学楼之一。\n\n");break;
case 3:
printf("3:图书馆\n\n 书籍的海洋，知识的乐园。\n\n");break;
case 4:
printf("4:综合楼\n\n 学生上课、实验的主要场所。\n\n");break;
case 5:
printf("5:体育馆\n\n 体育学院场馆。\n\n");break;
case 6:
printf("6:运动场\n\n 学生运动的乐园，设有田径场、足球场。\n\n");break;
case 7:
printf("7:学生宿舍\n\n 学校宿舍。\n\n");break;
case 8:
printf("8:莲花剧院\n\n 学院举办大型文艺活动的场所。\n\n");break;
case 9:
printf("9:青山湖\n\n 学校内的青山湖，风景优美。 \n\n");break;
case 10:
printf("10:文外学院\n\n 文学院与外国语学院的主要教学楼。\n\n");break;
default:
printf("景点编号输入错误！请输入1->10的数字编号！\n\n"); break;
}
}
int shortestdistance() /*要查找的两景点的最短距离*/
{
int i,j;
printf("请输入要查询的两个景点的编号(1->10的数字编号并用','间隔):");
scanf("%d,%d",&i,&j);
if(i>n||i<=0||j>n||j<0)
{
printf("输入信息错误！\n");
printf("请输入要查询的两个景点的编号(1->10的数字编号并用','间隔):");
scanf("%d,%d",&i,&j);
floyed();
display(i,j);
}
else
{
floyed();
display(i,j);
}
return 1;
}
void floyed() /*用floyed算法求两个景点的最短路径*/
{
int i,j,k;
for(i=1;i<=n;i++) //初始化
for(j=1;j<=n;j++)
{
shortest[i][j]=cost[i][j];
path[i][j]=0;
}
for(k=1;k<=n;k++) //n次递推
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(shortest[i][j]>(shortest[i][k]+shortest[k][j]))
{
/*得到新的最短路径长度数值*/
shortest[i][j]=shortest[i][k]+shortest[k][j];
path[i][j]=k;
path[j][i]=k; /*用path[][]记录从i到j的最短路径上点j的前驱景点的序号*/
}
}
void display(int i,int j) /*输出*/
{/* 打印两个景点的路径及最短距离 */
int a,b;
a=i;
b=j;
printf("您要查询的两景点间最短路径是:\n\n");
if(shortest[i][j]!=INT_MAX)
{
if(i<j)
{
printf("%d",b);
while(path[i][j]!=0)
{
/*把i到j的路径上所有经过的景点按逆序打印出来*/
printf("<-%d",path[i][j]);
j=path[i][j];
}
printf("<-%d",a);
printf("\n\n");
printf("(%d->%d)最短距离是:%d米\n\n",a,b,shortest[a][b]);
}
else
{
printf("%d",a);
while(path[i][j]!=0)
{
/* 把i到j的路径上所有经过的景点按顺序打印出来*/
printf("->%d",path[i][j]);
i=path[i][j];
}
printf("->%d",b);
printf("\n\n");
printf("(%d->%d)最短距离是:%5d米\n\n",a,b,shortest[a][b]);
}
}
else
printf("输入错误！不存在此路！\n\n");
printf("\n");
}
