#P6837. 法
法
题目描述
给定一张有 个顶点、 条边的无向连通图。每条边的长度均为 。求所有无序的不同顶点对之间的最短路长度之和。
输入格式
第一行两个整数 。接下来 行,每行两个整数 ,表示顶点 之间有一条边。顶点编号为 到 。
输出格式
输出一个整数,表示所有顶点对之间的最短路长度之和。
样例
4 4
1 2
2 3
3 1
3 4
8
7 10
1 2
2 6
5 3
5 4
5 7
3 6
1 7
5 1
7 4
4 1
34
数据范围
- 对于 20% 的数据,。
- 对于 40% 的数据,。
- 30% 的数据满足图为树,50% 的数据满足图为仙人掌。
- 对于所有数据,,。