图上的最短距离构成的路径的直径问题,采用C编程语言程序怎么实现

Problem Description
The graph diameter is the length of the "longest shortest path" between any two vertices of a graph. In other words, a graph's diameter is the longest path which must be traversed in order to travel from any vertex to another when paths which backtrack, detour, or loop are excluded from consideration.
Given an undirected graph, your mission is to count the number of diameters of it.

Input
The input contains multiple test cases.
For each test case, it contains n+1 lines.
Line 1: two integers m, n (2<= m <= 100, 1 <= n <= 4000) indicating that there are m vertices and n edges in the city.
Line 2~n+1: each contains three integers i, j, d (1 <= i, j <= m, 1 <= d <= 100), indicating that there is an edge of length d connecting vertex i and vertex j.

Output
Output the value of the diameter and the number of diameters in a single line, separated by a single space.

Sample Input
4 5
1 2 1
2 3 1
3 4 1
1 4 1
1 3 2

Sample Output
2 5

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐