#include"stdio.h"
#include"windows.h"
#define MAXV 14
#define INF 32767
typedef struct
{
    int edges[MAXV][MAXV];
    int n;
}MGraph;
int G[MAXV][MAXV]={
    {000,60,100,INF,INF,INF,40,INF,INF,INF,INF,INF,INF,INF},
    {60,000,INF,90,INF,INF,30,INF,INF,INF,INF,INF,INF,INF},
    {100,INF,000,INF,50,INF,INF,INF,80,INF,INF,INF,INF,INF},
    {INF,90,INF,000,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF},
    {INF,INF,50,INF,000,INF,INF,INF,50,INF,INF,INF,INF,INF},
    {INF,INF,INF,INF,INF,000,20,INF,40,20,INF,INF,INF,INF},
    {40,30,INF,INF,INF,20,000,130,INF,20,INF,INF,INF,INF},
    {INF,INF,INF,INF,INF,INF,130,000,INF,INF,INF,INF,110,INF},
    {INF,INF,80,INF,50,40,INF,INF,000,40,150,INF,INF,INF},
    {INF,INF,INF,INF,INF,20,20,INF,40,000,INF,170,INF,INF},
    {INF,INF,INF,INF,INF,INF,INF,INF,150,INF,000,200,INF,INF},
    {INF,INF,INF,INF,INF,INF,INF,INF,INF,170,200,000,200,180},
    {INF,INF,INF,INF,INF,INF,INF,110,INF,INF,INF,200,000,120},
    {INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,180,120,000}
};
MGraph r[]={"南门,逸夫楼,大礼堂,东门,物电楼,图书馆,灯光球场,校医院,多媒体,超市,大学生活动中心,五坡文化广场,民族餐厅,田径场"};
void Home()
{
    printf("\n----------欢迎使用广西民族大学校园导航系统----------\n");
    printf("\n     1-----路径查询             2-----各景点详细信息\n");
    printf("\n     3-----退出\n");
    printf("\n     请输入你的选择：   ");
}
void menu()
{
    printf("\n\n  1、南门        2、逸夫楼    3、大礼堂             4、东门\n");
    printf("\n  5、物电楼      6、图书馆    7、灯光球场           8、校医院\n");
    printf("\n  9、多媒体      10、超市     11、大学生活动中心    12、五坡文化广场\n");
    printf("\n  13、民族餐厅   14、田径场     \n");
}
/*void Pathquery()
{
    int a1,a2;
    menu();
    printf("\n所处位置:  ");
    scanf("%d",&a1);
    printf("\n目的地:   ");
    scanf("%d",&a2);
}*/
void Ppath(int path[],int i,int v)
{
    int k;
    k=path[i];
    if(k==v)
        return;
    Ppath(path,k,v);
    printf("%d,",k);
}
void Dispath1(int dist[],int path[],int s[],int v,int a)
{
    int i;
    if(s[a]==1)
    {if(i==dist[a])
        printf("从%d到%d的距离是:  %d\t\t路径为:",v,a,dist[a]);
        printf("%d,",v);
        Ppath(path,a,v);
        printf("%d\n",a);
    }
    else
        printf("从%d到%d不存在路径\n",v,a);
}
void Dijkstra1(MGraph g)
{
    int dist[MAXV],path[MAXV];
    int s[MAXV];
    int mindis,i,j,u;
    int v,a;
    printf("\n请输入任意两个顶点(1到14之间): ");
    scanf("%d\t%d",&v,&a);
    for(i=0;i<g.n;i++)
    {  
        dist[i]=g.edges[v][i];
        s[i]=0;
        if(g.edges[v][i]<INF)
            path[i]=v;
        else
            path[i]=-1;
    }
    s[v]=1;path[v]=0;
    for(i=0;i<g.n;i++)
    {   
        mindis=INF;
        for(j=0;j<g.n;j++)
            if(s[j]==0 && dist[j]<mindis)
            {
                u=j;
                mindis=dist[j];
            }
            s[u]=1;
            for(j=0;j<g.n;j++)
                if(s[j]==0)
                    if(g.edges[u][j]<INF && dist[u]+g.edges[u][j]<dist[j])
                    {   
                        dist[j]=dist[u]+g.edges[u][j];
                        path[j]=u;
                    }
    }
    Dispath1(dist,path,s,v,a);
}
void main()
{
    MGraph g;
    int a,x=1;
    Home();
    scanf("%d",&a);
    system("cls");
    while(x==1)
    {
        switch(a)
        {
        case 1:
            {
                system("cls");
                menu();
                g.n=MAXV;
                for(int i=0;i<MAXV;i++)
                    for(int j=0;j<MAXV;j++)
                        g.edges[i][j]=G[i][j];
                    Dijkstra1(g);
            }break;
        case 2:break;
        case 3:break;
        }printf("\n\n继续请按1，否则请按2:  ");
    scanf("%d",&x);   
    }
}