#include <iostream>
#include <string>
#include <iomanip>
using namespace std;

#define MAXVEX 15   //顶点数，应由用户定义
#define NUMBER 23   //边数，应由用户定义
#define INF 9999999 //定义一个无穷大数

struct Vexs
{
    string name; //地点名称
};

struct Graph
{
    Vexs vexs[MAXVEX];         //顶点表(以中文信息存储)结构体数组
    int arc[MAXVEX][MAXVEX];   //邻接矩阵，可看作边
    int numVertexes, numEdges; //图中当前的顶点数和边数
};

//事先把地图信息存储起来
//地点名称
string vexname[15] = {
    "大门",
    "教学区1",
    "图书馆",
    "结构楼",
    "煤炭楼",
    "教学区2",
    "体育馆",
    "田径场",
    "网球场",
    "男生宿舍楼",
    "女生宿舍楼",
    "学生超市",
    "骊秀苑",
    "榴馨苑",
    "综合楼"};
//初始化地点名称1
string loadingOne[23] = {
    "大门",
    "教学区1",
    "煤炭楼",
    "煤炭楼",
    "教学区2",
    "教学区2",
    "教学区1",
    "教学区1",
    "教学区1",
    "图书馆",
    "图书馆",
    "图书馆",
    "综合楼",
    "综合楼",
    "综合楼",
    "榴馨苑",
    "榴馨苑",
    "骊秀苑",
    "骊秀苑",
    "骊秀苑",
    "男生宿舍楼",
    "网球场",
    "网球场",
};
//初始化地点名称2
string loadingTwo[23] = {
    "教学区1",
    "煤炭楼",
    "结构楼",
    "教学区2",
    "田径场",
    "体育馆",
    "体育馆",
    "图书馆",
    "女生宿舍楼",
    "体育馆",
    "综合楼",
    "女生宿舍楼",
    "体育馆",
    "骊秀苑",
    "榴馨苑",
    "学生超市",
    "骊秀苑",
    "体育馆",
    "学生超市",
    "男生宿舍楼",
    "网球场",
    "田径场",
    "体育馆",
};
//初始化地点路程
int loadingNum[23] = {
    212,
    200,
    20,
    150,
    220,
    130,
    230,
    160,
    180,
    200,
    120,
    110,
    180,
    80,
    170,
    45,
    80,
    152,
    151,
    200,
    180,
    160,
    200,
};

//定位
int locates(Graph *g, string ch)
{
    int i = 0;
    for (i = 0; i < g->numVertexes; i++)
    {
        if (g->vexs[i].name == ch)
        {
            break;
        }
    }
    if (i >= g->numVertexes)
    {
        return -1;
    }
    return i;
}

//建立一个无向网图的邻接矩阵表示
void createGraph(Graph *g)
{

    int i, j, k, w;
    //初始化顶点数和边数
    g->numVertexes = MAXVEX; //15个顶点
    g->numEdges = NUMBER;    //22条边

    //初始化广东理工学院地点名称、代号、简介
    for (i = 0; i < g->numVertexes; i++)
    {
        g->vexs[i].name = vexname[i];
    }

    //邻接矩阵初始化为每个单元为INF
    for (i = 0; i < g->numVertexes; i++)
    {
        for (j = 0; j < g->numVertexes; j++)
        {
            g->arc[i][j] = INF;
        }
    }
    cout << endl;

    //初始化地图的各地点权值矩阵
    for (k = 0; k < g->numEdges; k++)
    {
        string p, q;
        p = loadingOne[k];
        q = loadingTwo[k];
        w = loadingNum[k];
        int m = -1;
        int n = -1;
        m = locates(g, p); //若m等于-1，说明在矩阵中并没有定位到
        n = locates(g, q);
        if (m == -1 || n == -1)
        {
            cout << "there is no vertex."<<loadingOne[k]<<" "<<loadingTwo[k]  << endl; //显示输入有错信息
            exit(-1);
        }
        g->arc[m][n] = w;
        g->arc[n][m] = w; //因为是无向图，矩阵对称
    }
}


//输出任一两点间的最短路径与长度
void Dispath(int dist[], int path[], int vv, int ee, Graph g) //输出从源点v出发的所有最短路径
{
    int i, j, k;
    int d; //存放一条最短路径（逆向）及其顶点个数
    string apath[MAXVEX];
    for (i = 0; i < g.numVertexes; i++) //n为顶点个数，循环n次，输出源点到其余各个顶点的最短路径和路径长度
    {
        if (i == ee)
        {
            cout << "从" << g.vexs[vv].name << "到" << g.vexs[ee].name << "的路径长度为:" << dist[i] << "\t路径为：";

            d = 0;
            apath[d] = g.vexs[i].name; //源点到i的最短路径上的终点为i，终点i存放在apath[0]
            k = path[i];               //源点到i的最短路径上，顶点i的前一个顶点为k
            if (k == -1)
                //没有路径的情况
                cout << "无路径\n";
            else //存在源点到i的最短路径时输出该路径
            {
                while (k != vv) //当k值等于源点编号时，循环结束
                {
                    d++;
                    apath[d] = g.vexs[k].name; //将源点v到i的最短路径上所经过的顶点编号，逆序存放在apath[d]
                    k = path[k];
                }
                d++;
                apath[d] = g.vexs[vv].name; //存储源点v到i的最短路径上的起点v

                cout << apath[d];            //先输出起点
                for (j = d - 1; j >= 0; j--) //再输出其他顶点
                {
                    cout << "->" << apath[j];
                }
            }
        }
    }
}
//求任一两地点之间的最短路径和长度
void shortestPath(Graph g, int v, int e)

{
    int vv = v;
    int ee = e;
    int dist[MAXVEX], path[MAXVEX];
    int F[MAXVEX];
    int mindis, i, j, u;
    for (i = 0; i < g.numVertexes; i++)
    {
        dist[i] = g.arc[v][i]; //距离初始化
        F[i] = 0;              //F[]置空
        if (g.arc[v][i] < INF) //路径初始化 等价于如果有边
            path[i] = v;       //顶点v到i有边时
        else
            path[i] = -1; //顶点v到i没边时
    }
    F[v] = 1;                           //源点v放入S中
    for (i = 0; i < g.numVertexes; i++) //循环n次
    {
        mindis = INF;
        for (j = 0; j < g.numVertexes; j++)
            if (F[j] == 0 && dist[j] < mindis)
            {
                u = j;
                mindis = dist[j];
            }
        //优化思路：如果F[ee]=1，那么程序就可以结束了
        F[u] = 1;                           //顶点u加入S中
        for (j = 0; j < g.numVertexes; j++) //修改不在s中的顶点的距离
            if (F[j] == 0)
                if (dist[u] + g.arc[u][j] < dist[j])
                {
                    dist[j] = dist[u] + g.arc[u][j];
                    path[j] = u;
                }
    }
    Dispath(dist, path, vv, ee, g); //输出最短路径
    cout << endl;
}

//功能实现
int function()
{
    Graph g;
    Graph *ptr = &g;
    createGraph(ptr); //邻接矩阵创建图
    int v, e;
    char chose;
    string str, start, end;
    while (true)
    {
        cout << "查询西科大任两个地点间的最短路径和长度" << endl;
        cout<<"以下为系统收录地点名称:"<<endl;
        for(int i=0;i<MAXVEX;i++)
        {
            cout<<vexname[i];
            cout<<"  ";
        }
        cout<<endl;

        cout << "请输入任意两地的名称，名称之间用空格隔开，以回车结束:" << endl;
        cin >> start >> end;
        v = locates(ptr, start);
        e = locates(ptr, end);
            if (v == -1 || e == -1)
            {
                cout << "查询地点发生错误,请重新操作!!!!" << endl;
            }
            else
            {
                shortestPath(g, v, e);
            }
            cout << endl;


        
        cin.ignore(100, '\n');
    }
}
int main(void)
{
    function();
    system("pause");
}