Untitled

#include <stdio.h>
#include <stdlib.h>
#include <string>
#define MAXSIZE 10
#define MAXINT 10000
using std::string;
int get_index(char *arr, char ch) //得到输入的字符在数组中的下标
{
    int i = 0;
    for (i = 0; i < MAXINT; i++)
    {
        if (arr[i] == ch)
            return i;
    }
    return -1;
}
void FindPath(int MiddleVer[MAXSIZE][MAXSIZE], int start, int end, string &path) //寻找经过的结点
{
    if (MiddleVer[start][end] == MAXINT) //说明start和end,两个顶点是直连的，中间没有别的顶点了
    {
        path += std::to_string(start) + "->";
    }
    else
    {                                                            //如果tart和end,两个顶点之间还有别的顶点
        FindPath(MiddleVer, start, MiddleVer[start][end], path); //则递归查找，从start位置到中间点位置的路径
        start = MiddleVer[start][end];
        while (MiddleVer[start][end] != MAXINT) //再查找从中间点位置到end位置之间的路径．
        {                                       //这里为什么不也用递归？是因为顺序的问题．这里如果也用递归，找出来的顶点顺序相反了．
            path += std::to_string(MiddleVer[start][end]) + "->";
            start = MiddleVer[start][end];
        }
    }
    path += std::to_string(end) + "->";
}

void floyd()
{
    int m, n, i, j, k;
    int n1, n2;
    char vertex[MAXSIZE];            //顶点数组
    int arcs[MAXSIZE][MAXSIZE];      //图的邻接矩阵，存储每一条边的权值
    int MiddleVer[MAXSIZE][MAXSIZE]; //存储每条边之间的中间点的下标，如果没有中间点，则值为MAXINT
    for (i = 0; i < MAXSIZE; i++)
    {
        for (j = 0; j < MAXSIZE; j++)
        {
            if (i == j)
                arcs[i][j] = 0;
            else
                arcs[i][j] = MAXINT;  //初始化每一条边
            MiddleVer[i][j] = MAXINT; //初始化每一条边的中间点
        }
    }
    scanf("%d%d", &m, &n);
    for (i = 0; i < n; i++)
    {
        scanf("%d%d%d", &n1, &n2, &k);
        arcs[n1][n2] = k;
        //如果是无向网，则要把对称点也赋上权值
        // arcs[get_index(vertex,ch2)][get_index(vertex,ch1)] = k;
    }
    // FLOYD算法核心
    for (k = 0; k < m; k++)
    {
        for (i = 0; i < m; i++)
        {
            for (j = 0; j < m; j++)
            {
                if (arcs[i][j] > arcs[i][k] + arcs[k][j])
                {
                    arcs[i][j] = arcs[i][k] + arcs[k][j];
                    MiddleVer[i][j] = k;
                }
            }
        }
    }
    int u, v;
    for (i = 0; i < 2; ++i)
    {
        scanf("%d%d", &u, &v);
        string path;
        FindPath(MiddleVer, u, v, path);
        path.pop_back();
        path.pop_back();
        if (arcs[u][v] != MAXINT)
            printf("%s:%d\n", path.c_str(), arcs[u][v]);
        else
            printf("%s:-1\n", path.c_str());
    }
    int max = 0;
    for (i = 0; i < m; i++)
    {
        for (j = 0; j < m; j++)
        {
            if (i != j && arcs[i][j] != MAXINT)
            {
                if (arcs[i][j] > max)
                {
                    max = arcs[i][j];
                }
            }
        }
    }
    bool outFlag=false;
    for (i = 0; i < m; i++)
    {
        if(outFlag)
            break;
        for (j = 0; j < m; j++)
        {
            if (i != j && arcs[i][j] != MAXINT)
            {
                if (arcs[i][j] == max)
                {
                    string path;
                    FindPath(MiddleVer, i, j, path);
                    path.pop_back();
                    path.pop_back();
                    printf("%s:%d", path.c_str(), arcs[i][j]);
                    outFlag=true;
                    break;
                }
            }
        }
    }
}
int main()
{
    floyd();
    return 0;
}