EXY-PG-0053
第 5 题
子图最短路
题目描述
给定包含 $n$ 个结点 $m$ 条边的带权无向图 $G$，结点依次以 $1,2,…,n$ 编号。第 $i (1≤i≤m)$ 条边连接编号为 $u_i$ 与 $v_i$ 的两个结点，权值为 $w_i$。
对于指定的 $1≤l≤r≤n$，按以下方式构造图 G 的子图 $G(l,r)$：
- 保留 $G$ 中编号在区间 $[l,r]$ 中的结点。删去其它编号不在 $[l,r]$ 中的结点以及与之相连的边。剩余的结点和边构成子图 $G(l,r)$。
对于 $G(l,r)$ 中的任意结点 $u,v$ 应有 $l≤u,v≤r$。记 u,v 在子图 $G(l,r)$ 上的最短距离为 $d(l,r,u,v)$。特殊地，若 $u,v$ 在子图 $G(l,r)$ 上不连通，则认为 $d(l,r,u,v)=0$。
你需要求出 $\sum_{l=1}^n \sum_{r=l}^n \sum_{u=l}^r \sum_{v=u}^r\,d(l,r,u,v)$ 对 $10^9$ 取模的结果。
- 题目中的英文字母 l 使用了特殊写法 $l$，以避免英文字母 l 与数字 1 混淆。
输入格式
第一行，两个正整数 $n,m$，表示结点数与边数。
接下来 $m$ 行，第 $i (1≤i≤m)$ 行包含三个正整数 $u_i,v_i,w_i$，表示一条连接结点 $u_i,v_i$ 的权值为 $w_i$ 的边。
输出格式
输出一行，一个整数，表示 $\sum_{l=1}^n \sum_{r=l}^n \sum_{u=l}^r \sum_{v=u}^r\,d(l,r,u,v)$ 对 $10^9$ 取模的结果。
样例说明
样例 1
输入：
3 2
1 2 1
2 3 2
输出：
9样例 2
输入：
4 6
1 2 100
2 3 100
3 4 100
1 3 10
2 4 10
1 4 1
输出：
784数据范围
对于 40% 的测试点，保证 $2≤n≤20$。
对于所有测试点，保证 $2≤n≤100，2≤m≤\frac{n(n-1)}{2}，1≤u_i,v_i≤n，1≤w_i≤10^6$。图中可能存在重边。
语言：
C++
GESP真题
八级
2026.3
编程题号：
2
当前页显示 5 - 5
，共 50 道编程题