#1799. 最短路求和
最短路求和
最短路求和
题目描述
标题: 最短路求和 - Problem - QOJ.ac
The problem was used in the following contests:
给定一个 n 个点 m 条边的无向连通图,边有非负边权,求 ∑i=2n∑j=1i−1dis(i,j),其中 dis(i,j) 表示点 i 到点 j 的最短路。
保证 m−n≤1000。
输入格式
第一行两个正整数 n,m。
接下来 m 行,每行三个非负整数 u,v,w 表示 u,v 间有一条长为 w 的边。保证没有重边自环。w≤104。
输出格式
一行一个非负整数,表示最短路和。
样例
样例输入 1
5 10
1 5 7
3 4 2
4 5 1
3 2 1
3 5 2
1 3 6
1 4 4
2 1 6
2 4 2
2 5 3
样例输出 1
32
数据范围与提示
子任务编号子任务限制分数1n≤300102m−n=−1103m−n=0104m−n≤20305m−n≤200106无特殊限制30
对于所有数据,2≤n≤105,m−n≤1000。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
5 10
1 5 7
3 4 2
4 5 1
3 2 1
3 5 2
1 3 6
1 4 4
2 1 6
2 4 2
2 5 3
32