shunfurh
编程介的小学生
采纳率92.7%
2017-07-19 15:20 阅读 732
已采纳

The diameter of graph

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条回答 默认 最新

相关推荐