2026年3月GESP真题及题解（C++八级）：子图最短路

2026年3月GESP真题及题解（C++八级）：子图最短路

题目描述

给定包含

n

n

n 个结点

m

m

m 条边的带权无向图

G

G

G，结点依次以

1

,

2

,

…

,

n

1, 2, \\dots, n

1,2,…,n 编号。第

i

i

i (

1

≤

i

≤

m

1 \\le i \\le m

1≤i≤m) 条边连接编号为

u

i

u_i

ui​ 与

v

i

v_i

vi​ 的两个结点，权值为

w

i

w_i

wi​。

对于指定的

1

≤

ℓ

≤

r

≤

n

1 \\le \\ell \\le r \\le n

1≤ℓ≤r≤n，按以下方式构造图

G

G

G 的子图

G

(

ℓ

,

r

)

G(\\ell, r)

G(ℓ,r)：

• 保留 $G$

对于

G

(

ℓ

,

r

)

G(\\ell, r)

G(ℓ,r) 中的任意结点

u

,

v

u, v

u,v 应有

ℓ

≤

u

,

v

≤

r

\\ell \\le u, v \\le r

ℓ≤u,v≤r。记

u

,

v

u, v

u,v 在子图

G

(

ℓ

,

r

)

G(\\ell, r)

G(ℓ,r) 上的最短距离为

d

(

ℓ

,

r

,

u

,

v

)

d(\\ell, r, u, v)

d(ℓ,r,u,v)。特殊地，若

u

,

v

u, v

u,v 在子图

G

(

ℓ

,

r

)

G(\\ell, r)

G(ℓ,r) 上不连通，则认为

d

(

ℓ

,

r

,

u

,

v

)

=

0

d(\\ell, r, u, v) = 0

d(ℓ,r,u,v)=0。

你需要求出

∑

ℓ

=

1

n

∑

r

=

ℓ

n

∑

u

=

ℓ

r

∑

v

=

u

r

d

(

ℓ

,

r

,

u

,

v

)

\\sum_{\\ell=1}^{n} \\sum_{r=\\ell}^{n} \\sum_{u=\\ell}^{r} \\sum_{v=u}^{r} d(\\ell, r, u, v)

∑ℓ=1n​∑r=ℓn​∑u=ℓr​∑v=ur​d(ℓ,r,u,v) 对

10

9

10^9

109 取模的结果。

• 题目中的英文字母 $l$

输入格式

第一行，两个正整数

n

,

m

n, m

n,m，表示结点数与边数。

接下来

m

m

m 行，第

i

i

i (

1

≤

i

≤

m

1 \\le i \\le m

1≤i≤m) 行包含三个正整数

u

i

,

v

i

,

w

i

u_i, v_i, w_i

ui​,vi​,wi​，表示一条连接结点

u

i

,

v

i

u_i, v_i

ui​,vi​ 的权值为

w

i

w_i

wi​ 的边。

输出格式

输出一行，一个整数，表示

∑

ℓ

=

1

n

∑

r

=

ℓ

n

∑

u

=

ℓ

r

∑

v

=

u

r

d

(

ℓ

,

r

,

u

,

v

)

\\sum_{\\ell=1}^{n} \\sum_{r=\\ell}^{n} \\sum_{u=\\ell}^{r} \\sum_{v=u}^{r} d(\\ell, r, u, v)

∑ℓ=1n​∑r=ℓn​∑u=ℓr​∑v=ur​d(ℓ,r,u,v) 对

10

9

10^9

109 取模的结果。

输入输出样例 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

说明/提示

对于

40

%

40\\%

40% 的测试点，保证

2

≤

n

≤

20

2 \\le n \\le 20

2≤n≤20。

对于所有测试点，保证

2

≤

n

≤

100

2 \\le n \\le 100

2≤n≤100，

2

≤

m

≤

n

(

n

−

1

)

2

2 \\le m \\le \\frac{n(n-1)}{2}

2≤m≤2n(n−1)​，

1

≤

u

i

,

v

i

≤

n

1 \\le u_i, v_i \\le n

1≤ui​,vi​≤n，

1

≤

w

i

≤

10

6

1 \\le w_i \\le 10^6

1≤wi​≤106。图中可能存在重边。

分析思路

题目要求计算所有区间 [l, r] 的诱导子图中所有点对 (u, v)（

u

≤

v

u \\le v

u≤v）的最短距离之和，不连通时距离为 0。 由于

n

≤

100

n \\le 100

n≤100，可以承受

O

(

n

4

)

O(n^4)

O(n4)的算法。 我们枚举左端点 l，然后按右端点 r 递增的顺序扩展区间。 维护当前区间的最短距离矩阵 d，初始时只包含节点 l。 当加入新节点 r 时，需要正确更新所有点对的最短距离，保证只使用编号在 [l, r] 内的节点作为中间节点。 具体步骤：

这样每个区间更新复杂度为

O

(

(

r

−

l

+

1

)

2

)

O((r-l+1)^2)

O((r−l+1)2)，总复杂度

O

(

n

4

)

≈

10

8

O(n^4) \\approx 10^8

O(n4)≈108，可以接受。

代码实现

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 105;
const ll INF = 1e18;
const int MOD = 1e9;

ll g[N][N]; // 原图邻接矩阵（最小边权）
ll d[N][N]; // 当前区间的最短距离矩阵

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
// 初始化邻接矩阵
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
g[i][j] = (i == j) ? 0 : INF;
// 读入边，保留最小权值
for (int i = 0; i < m; ++i) {
int u, v; ll w;
cin >> u >> v >> w;
if (w < g[u][v]) {
g[u][v] = w;
g[v][u] = w;
}
}

ll ans = 0;
// 枚举左端点
for (int l = 1; l <= n; ++l) {
// 初始化当前区间的最短距离矩阵为 INF
for (int i = l; i <= n; ++i)
for (int j = l; j <= n; ++j)
d[i][j] = INF;
d[l][l] = 0; // 初始只有一个节点
// 枚举右端点
for (int r = l; r <= n; ++r) {
if (r > l) {
// 1. 加入节点 r
d[r][r] = 0;
for (int i = l; i < r; ++i) {
d[i][r] = d[r][i] = g[i][r];
}
// 2. 用已有节点 k 更新到 r 的距离（允许中间节点 k）
for (int k = l; k < r; ++k) {
for (int i = l; i < r; ++i) {
if (d[i][k] < INF && d[k][r] < INF) {
ll nd = d[i][k] + d[k][r];
if (nd < d[i][r]) {
d[i][r] = d[r][i] = nd;
}
}
}
}
// 3. 以 r 为中间节点更新所有点对
for (int i = l; i <= r; ++i) {
for (int j = l; j <= r; ++j) {
if (d[i][r] < INF && d[r][j] < INF) {
ll nd = d[i][r] + d[r][j];
if (nd < d[i][j]) {
d[i][j] = nd;
}
}
}
}
}
// 4. 计算当前区间所有点对 (i<=j) 的距离和
ll sum = 0;
for (int i = l; i <= r; ++i) {
for (int j = i; j <= r; ++j) {
if (d[i][j] < INF) sum += d[i][j];
}
}
ans = (ans + sum) % MOD;
}
}
cout << ans << endl;
return 0;
}

功能分析

• 输入处理：使用邻接矩阵 g 存储最小边权，重边只保留最小值。
• 核心算法：枚举左端点 l，动态维护当前区间 [l, r] 的最短距离矩阵 d。每加入新节点 r 时，先通过直接边初始化，再用已有节点更新到 r 的距离，最后以 r 为中间节点更新所有点对。这样保证 d 始终是当前诱导子图的精确最短路。
• 复杂度：总操作次数约为 ${\sum }_{l=1}^n{\sum }_{r=l}^n(r-l+1{)}^2\approx \frac{n^4}{3}$

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<"########## 一站式掌握信奥赛知识! ##########";
cout<<"############# 冲刺信奥赛拿奖! #############";
cout<<"###### 课程购买后永久学习，不受限制! ######";
return 0;
}

【秘籍汇总】（完整csp信奥赛C++学习资料）：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

3、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划： https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL： https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践： https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转

4、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）： https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）： https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转

5、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）： https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<"跟着王老师一起学习信奥赛C++";
cout<<" 成就更好的自己！ ";
cout<<" csp信奥赛一等奖属于你! ";
return 0;
}