#include<stdio.h>
#include<process.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 main()
{/*主函数*/
int i,j;
char k;
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
cost[i][j]=INT_MAX;
cost[1][2]=cost[2][1]=68;
cost[1][5]=cost[5][1]=36;
cost[2][3]=cost[3][2]=16;
cost[2][4]=cost[4][2]=22;
cost[2][5]=cost[5][2]=40;
cost[2][10]=cost[10][2]=35;
cost[10][5]=cost[5][10]=50;
cost[3][4]=cost[4][3]=29;
cost[5][6]=cost[6][5]=21;
cost[6][10]=cost[10][6]=38;
cost[7][8]=cost[8][7]=28;
cost[7][9]=cost[9][7]=21;
cost[8][9]=cost[9][8]=12;
cost[6][7]=cost[7][6]=20;
cost[6][9]=cost[9][6]=29;
cost[9][10]=cost[10][9]=61;
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("****************欢迎使用常州工学院导游系统!*****************\n");
printf("------------------------------------------------------------\n");
printf("\ta.景点信息查询\n");
printf("\tb.景点最短路径查询\n");
printf("\tc.退出系统\n");
printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
printf("学校景点列表:\n");
printf("\t1:永远的127 \t2:小桥流水\n\t3:行政楼 \t4:学校西门\n");
printf("\t5:图书馆\t6:篮球场\n\t7:院士语林 \t8:院士楼\n");
printf("\t9:体育馆 \t10:秋白楼\n");
printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
printf("请选择所需服务:");
scanf("\n%c",&k);
switch(k)
{
case 'a':
printf("\t景点信息查询\n");
introduce();
break;
case 'b':
printf("\t最短路径查询\n:");
shortestdistance();
break;
case 'c':
printf("谢谢使用，祝您愉快！"); exit(0);
default:
printf("输入信息错误！请重新输入\n");printf("\n\n");
break;
}
}
}/*main*/
void introduce()
{/*景点介绍*/
int a;
printf("请输入您想查询的景点编号:");
scanf("%d",&a);
getchar();
printf("\n");
switch(a)
{
case 1:
printf("1:永远的127\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\n");break;
case 10:
printf("10:秋白楼\n\n 学校主教学楼之一，有大量实验室。\n\n");break;
default:
printf("景点编号输入错误！请输入1->10的数字编号！\n\n"); break;
}
}/*introduce*/
int shortestdistance()
{/*要查找的两景点的最短距离*/
int i,j;
printf("请输入要查询的两个景点的编号并用','间隔:");
scanf("%d,%d",&i,&j);
if(i>n||i<=0||j>n||j<0)
{
printf("输入信息错误！\n\n");
printf(" 请输入要查询的两个景点的编号并用','间隔:\n");
scanf("%d,%d",&i,&j);
}
else
{
floyed();
display(i,j);
}
return 1;
}/*shortestdistance*/
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++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(shortest[i][j]>(shortest[i][k]+shortest[k][j]))
{/*用path[][]记录从i到j的最短路径上点j的前驱景点的序号*/
shortest[i][j]=shortest[i][k]+shortest[k][j];
path[i][j]=k;
path[j][i]=k;
}
}/*floyed*/
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]);
if(i<j)
j=path[i][j];
else
i=path[j][i];
}
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]);
if(i<j)
j=path[i][j];
else
i=path[j][i];
}
printf("->%d",b);
printf("\n\n");
printf("(%d->%d)最短距离是:%5d米\n\n",a,b,shortest[a][b]);
}
}
else
printf("输入错误！不存在此路！\n\n");
printf("\n");
}/*display*/