| Time Limit: 2000MS | Memory Limit: 32768KB | 64bit IO Format: %I64d & %I64u |
Description
V11开了一家旅行社，众所周知现在商业竞争越来越激烈，为了更好地吸引消费者的眼球，v11决定制定到一条最短的旅游路线，路线的开始点和结束点必须是同一个地方。你的任务就是编写程序帮助v11寻找到这样的路线。
现在给出旅行路线图，图中有N个景点编号从1到N，有M条双向边编号从1到M。每条边包含三个数字A,B,C。表示这条路线连接景点A和景点B，他们之间的距离是C。为了简化问题，我们认为：每条旅游路线是一个至少包含三个点的简单回路。每条旅游路线的长度为它包含的所有边的距离之和。
现在的任务是：要求你编写程序寻找这样的最短路，给出它的路程长度，并输出同时存在有几个这样的最短路。
注意的是：
1.当两条最短路程中所经过的景点（不考虑顺序），完全相同时，才是相同的最短路程。否则，算作不同的最短路程。
2. 图的顶点序列中，除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫简单回路。（本题中将第一个顶点和最后一个顶点当作同一个景点）
3.本题中不存在自环。
Input
输入数据第一行包含一个整数T，表示测试数据的组数。对于每组测试数据：
第一行为两个整数n,m(1<n<100,1<m<5000)，接下来m行，每行三个整数a,b,v(1<=a,b<=n,1<v<500)，表示第i条路线连接景点A和景点B，距离是V。两个数字之间用空格隔开。
Output
对于每组测试数据：如果存在这样的最短路线，输出它的长度和不同的最短路线的个数。如果不存在则输出-1。两个数字之间用空格隔开，每组测试数据一行。
Sample Input
1 3 3 1 2 1 3 1 1 3 2 1
Sample Output
3 1
Hint
样例一中，我们可以从景点1出发的路线：1->2->3->1;
可以从景点2出发的路线：2->3->1->2;
同样也可以从景点3出发的路线:3->1->2->3;
我们认为这3条路线所经过的景点集合为{1,2,3}所以他们是相同的路线。
#include"string.h"
#include"stdio.h"
#include"math.h"
#define M 1111
#define inf 99999999
#include"iostream"
using namespace std;
int dis[M][M],G[M][M],n,mini,sum;
void floyd()
{
int i,j,k;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
dis[i][j]=G[i][j];
}
}
for(k=1;k<=n;k++)
{
for(i=1;i<k;i++)
{
for(j=1+i;j<k;j++)
{
if(mini>dis[i][j]+G[i][k]+G[k][j])
{
mini=dis[i][j]+G[i][k]+G[k][j];
sum=1;//记录最小环的个数
}
else if(mini==dis[i][j]+G[i][k]+G[k][j])
sum++;
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(dis[i][j]>dis[i][k]+dis[k][j])
dis[i][j]=dis[i][k]+dis[k][j];
}
}
}
}
int main()
{
int m,i,j;
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(i==j)
G[i][i]=0;
else
G[i][j]=inf;
}
}
while(m--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(G[a][b]>c)
G[a][b]=G[b][a]=c;
}
mini=inf;
floyd();
if(mini>=inf)
{
printf("-1
");
continue;
}
printf("%d %d
",mini,sum);
}
return 0;
}