#G1169. [GESP202603 八级] 子图最短路
[GESP202603 八级] 子图最短路
[GESP202603 八级] 子图最短路
题目描述
给定包含 个结点、 条边的带权无向图 ,结点依次以 编号。第 ()条边连接编号为 与 的两个结点,权值为 。
对于指定的 ,按以下方式构造图 的子图 :
- 保留 中编号在区间 中的结点。删去其它编号不在 中的结点以及与之相连的边。剩余的结点和边构成子图 。
对于 中的任意结点 ,应有 。记 在子图 上的最短距离为 。特殊地,若 在子图 上不连通,则认为 。
你需要求出 $\displaystyle\sum_{\ell=1}^{n}\sum_{r=\ell}^{n}\sum_{u=\ell}^{r}\sum_{v=u}^{r} d(\ell, r, u, v)$ 对 取模的结果。
题目中的英文字母 使用了特殊写法 ,以避免英文字母 与数字 混淆。
输入格式
第一行,两个正整数 ,表示结点数与边数。
接下来 行,第 ()行包含三个正整数 ,表示一条连接结点 的权值为 的边。
输出格式
输出一行,一个整数,表示 $\displaystyle\sum_{\ell=1}^{n}\sum_{r=\ell}^{n}\sum_{u=\ell}^{r}\sum_{v=u}^{r} d(\ell, r, u, v)$ 对 取模的结果。
样例 #1
样例输入 #1
3 2
1 2 1
2 3 2
样例输出 #1
9
样例 #2
样例输入 #2
4 6
1 2 100
2 3 100
3 4 100
1 3 10
2 4 10
1 4 1
样例输出 #2
784
数据范围
| 测试点 | 数据范围 | 说明 |
|---|---|---|
| 1~4 | 无 | |
| 全部 | ,,, | 图中可能存在重边 |