#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;
}