编程介的小学生 2019-01-11 15:31 采纳率: 0.4%
浏览 422
已采纳

利用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

  • 写回答

1条回答 默认 最新

  • threenewbee 2019-12-31 02:03
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?