#include<bits/stdc++.h>/** 注：步行速度为90m/min   **/
#define INFINITY 65535    ///无穷大，即不相邻
#define MAX_VERTEX_NUM 20 ///最大的顶点个数
using namespace std;
typedef int VRType;
typedef char InfoType;
typedef struct
{
    int num;
    char name[20];
    char introduce[100];
} VertexType;
typedef struct ArcCell
{
    VRType adj; ///距离
    InfoType *info;///边的信息
} ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
    VertexType vex[MAX_VERTEX_NUM];///顶点向量
    AdjMatrix arcs; ///邻接矩阵
    int vexnum,arcnum; ///顶点数和边数
} MGraph;
VertexType site[11]=
{
    {1,"生活区","  一大群孩子的老巢"},
    {2,"球场","    锻炼身体、休闲娱乐的地方"},
    {3,"风雨操场","情侣们秀恩爱的最佳去处"},
    {4,"众创空间","集合广播台等高大尚的工作的地方"},
    {5,"学苑超市","一个坑钱的地方，thing贼贵"},
    {6,"浴室","    让你出淤泥而不染的地方"},
    {7,"知味园","  小而拥挤、人流量te多还难吃的就餐地方"},
    {8,"致知楼","  结合上课和办公与一体的高端教学楼"},
    {9,"敏行楼","  夏天不热、冬天不冷的实验楼，也是报告厅所在地"},
    {10,"图书馆","  还在建设中，想进去都进不去"},
    {11,"学校南门","学校正门，学校的门面，然而基本没开过"}
};

/*****************************************************************************************************************/
/*****************************************************************************************************************/
/*******                                                                                                   *******/
/******/          void schoolmap();///学校地图                                                            /******/
/*******                                                                                                   *******/
/******/          void menu();///菜单                                                                      /******/
/*******                                                                                                   *******/
/******/          void create(MGraph &g,VertexType site[]);///创建邻接矩阵                                /******/
/*******                                                                                                   *******/
/******/          void output(MGraph g,int i);///根据序号i输出对应的地点的相关信息                      /******/
/*******                                                                                                   *******/
/******/          void search(MGraph g);///查找某个地点信息                                              /******/
/*******                                                                                                   *******/
/******/          void Shortest_Path_Dijkstra(MGraph g,int v0,int P[][20],int D[20]);///Dijkstra算法      /******/
/*******                                                                                                   *******/
/******/          void ShortestPath_FLOYD(MGraph g, int P[20][20][20], int D[][20]);///FLOYD算法          /******/
/*******                                                                                                   *******/
/******/          void add_arc(MGraph &g);///增加修改地点间路径                                          /******/
/*******                                                                                                   *******/
/******/          void delete_arc(MGraph &g);///删除某一条边                                              /******/
/*******                                                                                                   *******/
/******/          void display_num(MGraph g);///显示所有地点序号名称                                      /******/
/*******                                                                                                   *******/
/******/          void display_all(MGraph g);///输出具体信息                                              /******/
/*******                                                                                                   *******/
/******/          void update(MGraph &g);///修改某一个地点信息                                            /******/
/*******                                                                                                   *******/
/*****************************************************************************************************************/
/*****************************************************************************************************************/

int main()
{
    int v1,v2,P1[20][20],P2[20][20][20],D1[20],D2[20][20],i,j,k;
    MGraph g;
    create(g,site);
    printf("                  欢迎来到安科地图导航！                  \n");
    char admin[100]="admin",input[100];///用户名：admin
    char pass[100]="123456";///密码：123456
    char en[100];
L:
    printf("请输入用户名: ");
    scanf("%s",input);
    printf("请输入密码: ");
    scanf("%s",&en);
    if(!strcmp(admin,input)&&!strcmp(en,pass)) ;
    else
    {
        printf("用户名/密码错误，请重新输入，嘤嘤嘤qwq\n");
        goto L;
    }
LL1:
    menu();
    printf("please intput your choose：");
    scanf("%d",&i);
    switch(i)
    {
    case 0:
        schoolmap();
        goto LL1;
        break;
    case 1:
        display_num(g);
        goto LL1;
        break;
    case 2:
        display_all(g);
        goto LL1;
        break;
    case 3:
        search(g);
        goto LL1;
        break;
    case 4:
        printf("请输入地点的序号：\n");
        scanf("%d",&k);
        Shortest_Path_Dijkstra(g,k-1,P1,D1);
        for(i=1; i<g.vexnum; i++)
        {
            printf("%d号(%s)到%d号(%s)：",k,g.vex[k-1].name,i+1,g.vex[i].name);
            for(j=0; P1[i][j]!=-1; j++)
                printf("%d号(%s)  ",P1[i][j]+1,g.vex[P1[i][j]].name);
            printf("\n距离为：%d\n",D1[i]);
            puts("");
        }
        goto LL1;
        break;
    case 6:
        ShortestPath_FLOYD(g,P2,D2);
        for(i=0; i<g.vexnum; i++)
        {
            for(int j=0; j<g.vexnum; j++)
            {
                if(i!=j)
                {
                    if(D2[i][j]!=INFINITY)
                    {
                        cout<<g.vex[i].name<<"到"<<g.vex[j].name<<"的最短时间为："<<setw(5)<<D2[i][j]/90<<"min"<<", 最短路径为：";
                        for(int k=0; k<g.vexnum; k++)
                        {
                            if(P2[i][j][k]!=-1)
                                cout<<g.vex[P2[i][j][k]].name<<" ";
                            else
                                break;
                        }
                        puts("");
                    }
                    else
                        cout<<g.vex[i].name<<"到"<<g.vex[j].name<<"不可达"<<endl;
                }

            }
            puts("");
        }
        goto LL1;
        break;
    case 5:
        ShortestPath_FLOYD(g,P2,D2);
        for(i=0; i<g.vexnum; i++)
        {
            for(int j=0; j<g.vexnum; j++)
            {
                if(i!=j)
                {
                    if(D2[i][j]!=INFINITY)
                    {
                        cout<<g.vex[i].name<<"到"<<g.vex[j].name<<"的最短长度为："<<setw(5)<<D2[i][j]<<", 最短路径为：";
                        for(int k=0; k<g.vexnum; k++)
                        {
                            if(P2[i][j][k]!=-1)
                                cout<<g.vex[P2[i][j][k]].name<<" ";
                            else
                                break;
                        }
                        puts("");
                    }
                    else
                        cout<<g.vex[i].name<<"到"<<g.vex[j].name<<"不可达"<<endl;
                }

            }
            puts("");
        }
        goto LL1;
        break;
    case 7:
        add_arc(g);
        goto LL1;
        break;
    case 8:
        delete_arc(g);
        goto LL1;
        break;
    case 9:
        update(g);
        goto LL1;
        break;
    case 10:
        printf("下次再来玩呦，嘤嘤嘤^_^!\n");
        exit(0);
        goto LL1;
        break;
    default:
        printf("你的输入有误，请重新输入！嘤嘤嘤qwq\n");
        goto LL1;
        break;
    }
    return 0;
}
void menu()
{
    printf("************************************************************\n");
    printf("************************************************************\n");
    printf("***            0.大安科全景地图                          ***\n");
    printf("***            1.显示所有地点的序号                      ***\n");
    printf("***            2.查询所有地点的信息                      ***\n");
    printf("***            3.查询某个地点的具体信息                  ***\n");
    printf("***            4.查询某个地点到其他地点的最短路径        ***\n");
    printf("***            5.输出任意两个地点之间的最短路径          ***\n");
    printf("***            6.输出任意两个地点之间的最短时间          ***\n");
    printf("***            7.增加某一条边                            ***\n");
    printf("***            8.删除某一条边                            ***\n");
    printf("***            9.修改某个地点的具体信息                  ***\n");
    printf("***            10.退出系统                               ***\n");
    printf("************************************************************\n");
    printf("************************************************************\n");
}
void schoolmap()
{
    printf("                                    安科平面图                                 \n");
    printf(" *----------------------------------------------------------------------------*\n");
    printf(" |                             |西门|                                         |\n");
    printf(" |----------------------------------------------------------------------------|\n");
    printf(" | *----------------* *-----------------* *--------------------------------*  |\n");
    printf(" | |                | |                 | |           生活区  (1)          |  |\n");
    printf(" | |    风    雨    | |                 | | *----*  *----*  *----*  *----* |  |\n");
    printf(" | |                | |                 | | | 德 |  | 德 |  | 德 |  | 德 | |  |\n");
    printf(" | |    操    场    | |     球场  (2)   | | | 馨 |  | 馨 |  | 馨 |  | 馨 | |  |\n");
    printf(" | |                | |                 | | | 苑 |  | 苑 |  | 苑 |  | 苑 | |  |\n");
    printf(" | |       (3)      | |                 | | | 1  |  | 2  |  | 3  |  | 4  | |  |\n");
    printf(" | |                | |                 | | *----*  *----*  *----*  *----* |  |\n");
    printf(" | *----------------* *-----------------* *--------------------------------*  |\n");
    printf(" |                     *-----------------------*              *----------*    |\n");
    printf(" |                     |  间  |    市    |  室 |              | *------* |    |\n");
    printf(" |                     |  空  |    超    |     |              | |  B   | |    |\n");
    printf(" |                     |  创  |    苑    |     |              | |  园  | |    |\n");
    printf(" |                     |  众  |    学    |  浴 |              | |      | |    |\n");
    printf(" |                     | （4）|  （5）   |（6）|              | |  味  | |    |\n");
    printf(" |                     *-----------------------*              | |      | |    |\n");
    printf(" |                                                  *---------* |  知  | |    |\n");
    printf(" |                                                  |  *--------*      | |    |\n");
    printf(" |                                                  |  |               | |    |\n");
    printf(" |                                                  |  |   知味园A     | |    |\n");
    printf(" |       *-----------------------------------*      |  |               | |    |\n");
    printf(" |       |  *--------*  *--------* *-------* |      |  *---------------* |    |\n");
    printf(" |       |  |        |  |        | |       | |      |      （7）         |    |\n");
    printf(" |       |  |   A    |  |    B   | |   C   | |      *--------------------*    |\n");
    printf(" |       |  |   楼   |  |    楼  | |   楼  | |                                |\n");
    printf(" |       |  |   知   |  |    知  | |   知  | |                                |\n");
    printf(" |       |  |   致   |  |    致  | |   致  | |                                |\n");
    printf(" |       |  |        |  |        | |       | |                                |\n");
    printf(" |       |  *--------*  *--------* *-------* |                                |\n");
    printf(" |-----* |                (8)                |            *----------*        |\n");
    printf(" | 门  | *-----------------------------------*            |          |        |\n");
    printf(" | (11)|                                                  |    馆    |        |\n");
    printf(" |     |                                                  |    书    |        |\n");
    printf(" | 南  |                                                  |    图    |        |\n");
    printf(" |-----* *-------------------------------------*          |   (10)   |        |\n");
    printf(" |       |               (9)                   |          *----------*        |\n");
    printf(" |       |  *--------*  *--------* *-------*   |                              |\n");
    printf(" |       |  |        |  |        | |       |   |                              |\n");
    printf(" |       |  |   A    |  |    B   | |   C   |   |                              |\n");
    printf(" |       |  |   楼   |  |    楼  | |   楼  |   |                              |\n");
    printf(" |       |  |   行   |  |    行  | |   行  |   |                              |\n");
    printf(" |       |  |   敏   |  |    敏  | |   敏  |   |                              |\n");
    printf(" |       |  |        |  |        | |       |   |                              |\n");
    printf(" |       |  *--------*  *--------* *-------*   |       |  东   门  |          |\n");
    printf(" *-------*-------------------------------------*-------*-----------*----------*\n");
    printf("\n");
}
void create(MGraph &g,VertexType site[])
{
    int i,j;
    g.vexnum=11;
    g.arcnum=12;
    for(i=0; i<11; i++)
        g.vex[i]=site[i];
    for(i=0; i<g.vexnum; i++)
        for(j=0; j<g.vexnum; j++)
            g.arcs[i][j]= {INFINITY,NULL};
    g.arcs[0][1].adj=150;
    g.arcs[1][2].adj=100;
    g.arcs[2][3].adj=141;
    g.arcs[3][4].adj=30;
    g.arcs[4][5].adj=30;
    g.arcs[5][9].adj=300;
    g.arcs[5][10].adj=410;
    g.arcs[6][7].adj=210;
    g.arcs[6][9].adj=180;
    g.arcs[0][4].adj=160;
    g.arcs[0][7].adj=400;
    g.arcs[9][10].adj=310;
    g.arcs[7][8].adj=190;
    for(i=0; i<g.vexnum; i++)
        for(j=0; j<g.vexnum; j++)
            g.arcs[j][i].adj= g.arcs[i][j].adj;
}
void output(MGraph g,int i)
{
    printf("地点序号：%d\n",i);
    printf("地点名称：%s\n",g.vex[i-1].name);
    printf("地点简介：%s\n",g.vex[i-1].introduce);
}
void search(MGraph g)
{
    int i;
    printf("请输入你想查找地点的序号：");
    scanf("%d",&i);
    output(g,i);
}
void Shortest_Path_Dijkstra(MGraph g,int v0,int P[][20],int D[20])
{

    int v,w,i,j,final[20],min;
    for(v=0; v<g.vexnum; v++)
    {
        final[v]=0;
        D[v]=g.arcs[v0][v].adj;
        for(w=0; w<g.vexnum; w++)
            P[v][w]=-1;
        if(D[v]<INFINITY)
        {
            P[v][0]=v0;
            P[v][1]=v;
        }
    }
    D[v0]=0;
    final[v0]=1;
    for(i=1; i<g.vexnum; i++)
    {
        min=INFINITY;
        for(w=0; w<g.vexnum; w++)
            if(!final[w]&&D[w]<min)
            {
                v=w;
                min=D[w];
            }
        final[v]=1;
        for(w=0; w<g.vexnum; w++)
            if(!final[w]&&(min+g.arcs[v][w].adj<D[w]))
            {
                D[w]=min+g.arcs[v][w].adj;
                for(j=0; j<g.vexnum; j++)
                {
                    P[w][j]=P[v][j];
                    if(P[w][j]==-1)///在p[w][]第一个等于-1的地方加上顶点w
                    {
                        P[w][j]=w;
                        break;
                    }
                }
            }
    }
}
void ShortestPath_FLOYD(MGraph g, int P[20][20][20], int D[][20])
{
    int u,v,w,i,j;
    for(v=0; v<g.vexnum; v++)
        for(w=0; w<g.vexnum; w++)
        {
            D[v][w]=g.arcs[v][w].adj;
            for(u=0; u<g.vexnum; u++)
                P[v][w][u]=-1;
            if(D[v][w]<INFINITY)
            {
                P[v][w][0]=v;
                P[v][w][1]=w;
            }
        }

    for(u=0; u<g.vexnum; u++)
        for(v=0; v<g.vexnum; v++)
            for(w=0; w<g.vexnum; w++)
                if(D[v][u]<INFINITY&&D[u][w]<INFINITY&&D[v][u]+D[u][w]<D[v][w])
                {
                    ///更新D
                    D[v][w]=D[v][u]+D[u][w];
                    ///更新p，从v到w的路径是从v到u，再从u到w的所有路径
                    for(i=0; i<g.vexnum; i++)
                    {
                        if(P[v][u][i]!=-1)
                            P[v][w][i]=P[v][u][i];
                        else
                            break;
                    }
                    for(j=1; j<g.vexnum; j++) ///注意：这里j从1开始而不是从0开始，因为从v到u的路径最后一个顶点是u, 而从u到w的路径第一个顶点是u，只需打印u一次即可。
                    {
                        if(P[u][w][j]!=-1)
                            P[v][w][i++]=P[u][w][j];
                        else
                            break;
                    }

                }

}
void update(MGraph &g)
{
    int i;
    printf("请输入你想查找的地点的序号：");
    scanf("%d",&i);
    if(i>=1&&i<=11)
    {
        printf("请输入新的地点名称：");
        scanf("%s",g.vex[i-1].name);
        printf("请输入新的地点名称简介：");
        scanf("%s",g.vex[i-1].introduce);
    }
    else printf("没有找到这个地方嘤嘤嘤qwq~\n");
}
void add_arc(MGraph &g)
{
    int v1,v2,n;
    printf("请输入你想增加的边两端的顶点序号：");
    printf("请输入第一个顶点号：");
    scanf("%d",&v1);
    printf("请输入第二个顶点号：");
    scanf("%d",&v2);
    if(g.arcs[v1-1][v2-1].adj==INFINITY)
    {
        printf("请输入两点之间的距离：");
        scanf("%d",&g.arcs[v1-1][v2-1].adj);
        g.arcs[v2-1][v1-1].adj=g.arcs[v1-1][v2-1].adj;
        printf("增加成功！嘤嘤嘤^_^\n");
    }
    else
    {
LL0:
        printf("这两点已经有路径存在了，你想要修改它吗？想的话请按1，不想请按2：\n");
        scanf("%d",&n);
        if(n==1)
        {
            printf("请输入两点之间的新的距离：");
            scanf("%d",&g.arcs[v1-1][v2-1].adj);
            g.arcs[v2-1][v1-1].adj=g.arcs[v1-1][v2-1].adj;
            printf("修改成功！嘤嘤嘤^-^\n");
        }
        else if(n==2)
        {
            printf("增加失败，嘤嘤嘤T_T\n");
        }
        else
        {
            printf("你的输入有误，请重新输入！嘤嘤嘤qwq\n");
            goto LL0;
        }
    }
}
void delete_arc(MGraph &g)
{
    int v1,v2;
    printf("请输入你想删除的边两端的顶点序号：\n");
    printf("请输入第一个顶点号：\n");
    scanf("%d",&v1);
    printf("请输入第二个顶点号：\n");
    scanf("%d",&v2);
    if(g.arcs[v1-1][v2-1].adj!=INFINITY)
    {
        g.arcs[v1-1][v2-1].adj=g.arcs[v2-1][v1-1].adj=INFINITY;
        printf("删除成功！嘤嘤嘤^_^\n");
    }
    else
        printf("删除失败！这两个点之间本来就没有直接通路，你还删它干嘛？！嘤嘤嘤qwq\n");
}
void display_num(MGraph g)
{
    int i;
    printf("<地点序号>   <地点名称>\n");
    for(i=0; i<g.vexnum; i++)
        printf("%5d        %s\n",g.vex[i].num,g.vex[i].name);
}
void display_all(MGraph g)
{
    int i;
    printf("<地点序号>   <地点名称>          <地点简介>\n");
    for(i=0; i<g.vexnum; i++)
    {
        printf("%5d        %s            %s\n",g.vex[i].num,g.vex[i].name,g.vex[i].introduce);
    }
}