GESP 题解库 / 8 级题解 / [GESP202603 八级] 子图最短路 · 第 1 / 24 题
GESP202603 八级 · P15805 · 困难

子图最短路

固定左端点 ℓ,让右端点 r 从 ℓ 一路长到 n;每加入一个点 k,就用 k 作中间点补一次 Floyd 松弛,并把子图 G(ℓ, k) 的点对距离全部累加。

🕸️
n ≤ 100
结点数(m ≤ n(n−1)/2)
🧮
四重求和
所有子图的所有点对
⚡
O(n⁴) ≈ 2.5 × 10⁷
递增 Floyd 的运算量
🎯
固定 ℓ + 增量 Floyd
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

给定包含 n 个结点 m 条边的带权无向图 G,结点依次以 1, 2, …, n 编号。第 i(1 ≤ i ≤ m)条边连接编号为 uᵢ 与 vᵢ 的两个结点,权值为 wᵢ。

对于指定的 1 ≤ ℓ ≤ r ≤ n,按以下方式构造图 G 的子图 G(ℓ, r):

对于 G(ℓ, r) 中的任意结点 u, v 应有 ℓ ≤ u, v ≤ r。记 u, v 在子图 G(ℓ, r) 上的最短距离为 d(ℓ, r, u, v)。特殊地,若 u, v 在子图 G(ℓ, r) 上不连通,则认为 d(ℓ, r, u, v) = 0。

你需要求出 Σℓ=1…n Σr=ℓ…n Σu=ℓ…r Σv=u…r d(ℓ, r, u, v) 对 10⁹ 取模的结果。

输入格式

第一行,两个正整数 n, m,表示结点数与边数。
接下来 m 行,第 i(1 ≤ i ≤ m)行包含三个正整数 uᵢ, vᵢ, wᵢ,表示一条连接结点 uᵢ, vᵢ 的权值为 wᵢ 的边。

输出格式

输出一行,一个整数,表示上述四重求和对 10⁹ 取模的结果。

输入输出样例 #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 ≤ n(n−1)/2,1 ≤ uᵢ, vᵢ ≤ n,1 ≤ wᵢ ≤ 10⁶。图中可能存在重边。

💡
人话翻译:把"编号恰好落在 [ℓ, r] 里"的那些点单独抠出来,连同两端都在区间内的边,得到一张小子图 G(ℓ, r)。
在这张小子图里,任意两点 u, v 都有一个最短距离;不连通就记 0。
题目要你把每一张子图里每一对点的最短距离全部加起来。
两个不起眼但很致命的细节:① u = v 的距离恒为 0,加了也白加,所以只统计 u < v;② "不连通记 0"意味着这些点对直接当作 0 贡献,不需要任何特判。
朴素做法是"对每张子图重建 + 跑一遍 Floyd",共 O(n⁵) ≈ 10¹⁰,必定超时。
正解:固定 ℓ,让 r 从 ℓ 一点点长大到 n。相邻两张子图只差一个点,所以每次只用新点补一次松弛就行。

🔍 关键词提取

带权无向图诱导子图全源最短路四重求和增量 Floyd重边取最小

已知条件

项目说明
输入第一行 n、m;随后 m 行每行 u、v、w
输出四重求和对 10⁹ 取模
数据范围2 ≤ n ≤ 100,2 ≤ m ≤ n(n−1)/2
边权1 ≤ wᵢ ≤ 10⁶,图中可能有重边
子图定义保留编号在 [ℓ, r] 内的点,以及两端都在区间内的边
距离约定不连通时 d = 0;u = v 时 d = 0
统计口径每张子图只累加 u < v 的点对

需要解决的问题

02
思维导图
整理解题思路的全貌
🕸️ 固定 ℓ,让 r 长大:子图只会"多一点"
🧠 问题拆解
子图数量 = n(n+1)/2 张
每张要全源最短路
只统计 u < v 的点对
不连通按 0 计
🔁 增量技巧
固定 ℓ,r 从 ℓ 递增到 n
新点 r 只可能"缩短"经过它的路径
用 r 当中间点补一次松弛
松弛要在整个 [ℓ, n] 上做
✅ 为什么够快
每张子图只花 O(n²)
合计 O(n⁴) ≈ 2.5 × 10⁷
重边在邻接矩阵里取最小
距离用 long long,不取模
⚠️ 易错点
每次忘了重新拷贝邻接矩阵
松弛范围只写到 r(后续会算错)
把 INF 当 0 累加进答案
把 u = v 的对也统计进去
03
样例手算推导
样例 1 与样例 2 的逐张子图推演

🧮 样例 1:n = 3,一条链 1 — 2 — 3

边:1–2 (w = 1)、2–3 (w = 2)。把 6 张子图逐张算一遍,看看 9 是怎么来的。

(ℓ, r)子图里有谁各点对距离(不连通记 0)小计
(1, 1)只留点 1没有 u < v 的点对0
(1, 2)点 1、2,边 1–2d(1,2) = 11
(1, 3)点 1、2、3,两条边d(1,2) = 1,d(1,3) = 3,d(2,3) = 26
(2, 2)只留点 2没有点对0
(2, 3)点 2、3,边 2–3d(2,3) = 22
(3, 3)只留点 3没有点对0
1
为什么 (1, 3) 里 d(1,3) = 3

1 到 3 只能走 1 → 2 → 3

长度 1 + 2 = 3

(没有直连边,更没有别的绕法)

✅ 3

2
把 6 张小计相加

0 + 1 + 6 + 0 + 2 + 0

= 9

✅ 与样例输出一致

🔑
注意 (1, 2) 与 (2, 3):同一对点 (2, 3) 在 G(1, 3) 里距离是 2,在 G(2, 3) 里距离也是 2,但它们属于不同的子图,要分别统计——求和式里的外层两个 Σ 就是在遍历所有子图。
反过来,同一张子图内的 (u, v) 与 (v, u) 是同一个距离,所以内层写成 v = u … r,避免重复计数。

🧮 样例 2:n = 4、6 条边,答案 784

边为 1–2 (100)、2–3 (100)、3–4 (100)、1–3 (10)、2–4 (10)、1–4 (1)。这张图每加一个点,都会出现新的"抄近路",正好检验增量思想。

(ℓ, r)点对距离小计
(1, 1)—0
(1, 2)d(1,2) = 100100
(1, 3)d(1,2) = 100,d(1,3) = 10,d(2,3) = 100210
(1, 4)d(1,2) = 11,d(1,3) = 10,d(1,4) = 1,d(2,3) = 21,d(2,4) = 10,d(3,4) = 1164
(2, 2)—0
(2, 3)d(2,3) = 100100
(2, 4)d(2,3) = 100,d(2,4) = 10,d(3,4) = 100210
(3, 3)—0
(3, 4)d(3,4) = 100100
(4, 4)—0
1
第 1 阶段:G(1, 3) 里 1 与 3 直接连通

G(1, 2) 只有边 1–2,所以 d(1,2) = 100

加入点 3 后,边 1–3 (10) 可用

d(1,3) = 10;而 d(2,3) 只能绕 2 → 1 → 3 = 100 + 10 = 110 吗?

别忘了还有原边 2–3 (100),所以 d(2,3) = 100

小计 100 + 10 + 100 = 210

✅ 210

2
第 2 阶段:G(1, 4) 里点 4 成了"枢纽"

加入点 4 后新边:2–4 (10)、1–4 (1)

d(1,4) = 1(直连最短)

d(1,2):min(100, 1 + 10) = 11

d(3,4):min(100, 3 → 1 → 4 = 10 + 1) = 11

d(2,3):min(100, 2 → 4 → 3 = 10 + 100, 2 → 4 → 1 → 3 = 10 + 1 + 10) = 21

d(2,4) = 10

小计 11 + 10 + 1 + 21 + 10 + 11 = 64

✅ 64

3
第 3 阶段:把 10 张小计加起来

0 + 100 + 210 + 64 + 0 + 100 + 210 + 0 + 100 + 0

= 784

✅ 与样例输出一致

⚠️
这里藏着本题最关键的细节:在 G(1, 4) 里,d(2, 3) 的最短路是 2 → 4 → 1 → 3,同时用到了"更大的编号 4"和"更小的编号 1"。
这说明"新加入的点"不仅自己参与,还会把老点之间的距离也改短。所以增量算法里,每加一个点都必须重新松弛所有老点对,不能只更新"和 new 有关的距离"。
04
解法对比
增量 Floyd vs 逐张子图重建 vs 对每个点单源最短路

⚔️ 解法对比

🟢 固定 ℓ + 增量 Floyd(推荐) 推荐

固定左端点 ℓ,把矩阵限制在 [ℓ, n] 跑 Floyd;中间点 k 每前进一步,就把子图 [ℓ, k] 的点对距离累加进答案

  • 时间 O(n⁴) ≈ 2.5 × 10⁷(n = 100)
  • 空间 O(n²),只有两张 100 × 100 的矩阵
  • 代码约 40 行
  • 答案边算边累加,不需要保存
💡
为什么限制在 [ℓ, n] 而不是 [ℓ, k]?因为后面还会加入编号更大的点,它们需要用 d[i][k] 这些"和 k 有关的距离"继续松弛。
把范围留到 n,就保证了后续每一步都能拿到已经用 [ℓ, k−1] 里的点算好的距离。

🟠 逐张子图重建 + Floyd

对每一对 (ℓ, r) 重新抠出子图,跑一次全源最短路

  • 时间 O(n⁵) ≈ 10¹⁰
  • 空间 O(n²)
  • 代码最短、最好写
  • 40% 部分分(n ≤ 20)可以拿
⚠️
它慢在哪:子图一共 n(n+1)/2 张,每张都要 O(n³),
而相邻两张子图的差别只有一个点——把上一张的结果丢掉重算,等于把 99% 的工作量白扔了。

📈 性能对比

方案复杂度代码量
固定 ℓ + 增量 FloydO(n⁴) ≈ 2.5 × 10⁷约 40 行 ✅ 推荐
逐张子图重建 + FloydO(n⁵) ≈ 10¹⁰约 35 行 ❌ 超时
每个点各跑一次 DijkstraO(n · n² log n) 单张,整体 O(n⁶)约 60 行 ❌ 更慢
05
算法流程图
固定 ℓ 的"子图长大"主流程
开始读入 n、m 与 m 条边(重边只在矩阵里留最小权)枚举左端点 ℓ = 1 … n把 [ℓ, n] 的邻接矩阵拷进工作矩阵 d枚举中间点 k = ℓ … n(k 就是"新加入的点 r")用 k 松弛所有 i、j ∈ [ℓ, n]:d[i][j] = min(d[i][j], d[i][k] + d[k][j])把子图 G(ℓ, k) 中所有 u < v 的 d[u][v] 累加进答案(不可达记 0)k 还没到 n 吗?是 ✓k 加一,子图继续长大否 ✗换下一个 ℓ 重来ℓ 还没到 n 吗?输出答案对 10⁹ 取模k 加一:子图 [ℓ, k] 再多一个点
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🕸️ 子图最短路求和器(固定 ℓ + 增量 Floyd)

第一行输入 n m,随后 m 行输入 u v w(允许重边)。程序会按"固定 ℓ、r 递增"的顺序逐张子图累加点对距离,并列出每张子图的小计与累计答案。为便于观察,演示规模限制 n ≤ 6。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(固定 ℓ + 增量 Floyd)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll INF = (ll)1e15;          // 最短路最大约 99 × 10⁶,1e15 足够当无穷大
const ll MOD = 1000000000LL;

int n, m;
ll g[105][105];                   // 原图邻接矩阵(重边只留最小)
ll d[105][105];                   // 当前 Floyd 的工作矩阵

int main() {
    scanf("%d %d", &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;
        scanf("%d %d %lld", &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++) {
        // 1) 把 G(l, l) 的矩阵搬进来,之后让它"慢慢长大"
        for (int i = l; i <= n; i++)
            for (int j = l; j <= n; j++)
                d[i][j] = g[i][j];

        for (int k = l; k <= n; k++) {
            // 2) 用刚加入的结点 k 作中间点松弛(范围留在 [l, n],供后续继续用)
            for (int i = l; i <= n; i++) {
                if (d[i][k] >= INF) continue;
                ll dik = d[i][k];
                for (int j = l; j <= n; j++)
                    if (dik + d[k][j] < d[i][j])
                        d[i][j] = dik + d[k][j];
            }
            // 3) 此刻 d 在 [l, k] 上就是 G(l, k) 的全源最短路,累加 u < v
            for (int u = l; u <= k; u++)
                for (int v = u + 1; v <= k; v++)
                    if (d[u][v] < INF)
                        ans = (ans + d[u][v]) % MOD;
        }
    }

    printf("%lld\n", ans % MOD);
    return 0;
}
🔑
三个要点:① 每换一个 ℓ 都要重新从 g 拷一遍矩阵,因为上一轮的 ℓ 用过的旧数据必须全部丢弃;② 松弛范围是 [ℓ, n] 而不是 [ℓ, k],这样后面加入的点才能继承到正确的中间结果;③ 距离不要取模,只在累加进答案时取模——取模后的距离会破坏 min 的比较。

📖 关键几行怎么看

代码作用为什么这样写
if (w < g[u][v]) { g[u][v] = w; g[v][u] = w; }重边取最小题目说可能有重边,只留最短那条对最短路才有意义
d[i][j] = g[i][j];(范围 [l, n])初始化子图每个 ℓ 都从"只有直连边"的状态重新出发
if (d[i][k] >= INF) continue;剪掉不可达否则 INF + 边权 参与比较毫无意义,还容易溢出
for (int u = l; u <= k; u++) for (int v = u + 1; …)累加点对只统计 u < v,避免同一距离被加两次
if (d[u][v] < INF)不连通记 0不可达的距离按题意算 0,直接跳过即可
ans = (ans + d[u][v]) % MOD;边算边取模答案可能极大,累加时就取模才不会溢出
⚠️
四个坑:① 松弛范围写成 [ℓ, k]——当下没错,但后面加入更大的点时 d[i][k] 已经过时,答案会偏大;② 忘了重边取最小,用"最后读到的边"覆盖,遇到重边就错;③ 把 INF 也累加进答案,那种"不连通"的点对必须当 0 跳过;④ 对距离提前取模,min 的比较被破坏,结果完全不可信。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
3 2
1 2 1
2 3 2
9题面样例 1:链式子图,逐张累加得 9
4 6
1 2 100
2 3 100
3 4 100
1 3 10
2 4 10
1 4 1
784题面样例 2:点 4 加入后老点对也会被改短
2 2
1 2 5
1 2 3
3重边:两点的子图里只认最短那条 3
4 2
1 2 1
3 4 1
6子图可能不连通:不连通点对一律记 0
2 2
1 2 1000000
1 2 1000000
1000000边权取到上限 10⁶,验证不会溢出
5 4
1 2 1
2 3 1
3 4 1
4 5 1
56最长链:所有点对距离都要算,考察累加次数
100 4950 完全图(边权随机)运行验证最大规模,考察 O(n⁴) 是否跑得动
✅
自查清单:① 每个 ℓ 都重新拷矩阵了吗?② 松弛范围是 [ℓ, n] 吗?③ 只累加 u < v 吗?④ 不连通的距离跳过了吗?

🚨 易错点清单

⚠️
松弛范围写成 [ℓ, k]:样例 2 就会挂——G(1, 4) 里 d(2, 3) 要用到点 4 与点 1 的中间结果。
⚠️
忘记每轮重新拷矩阵:上一个 ℓ 算出的距离会残留,答案偏小(距离偏小)。
⚠️
重边只留最后一条:重边里往往有更短的,必须 min 一下。
⚠️
把不连通当无穷大累加:题意是"不连通记 0",必须跳过而不是加上一个巨大数字。
⚠️
距离提前取模:min 的比较依赖真实大小,取模后答案必错。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n⁴)
空间复杂度
O(n²)
n = 100 时运算量
约 2.5 × 10⁷
距离量级
≤ 99 × 10⁶

时间怎么算的?

空间都用在哪?

只需要两张 101 × 101 的矩阵:g 保存原图(重边取最小),d 作为 Floyd 的工作矩阵。答案用 long long 边算边取模,不需要存任何中间结果。

✅ 2.5 × 10⁷ 量级在 C++ 里不到 0.1 秒,关键就是把 O(n⁵) 的"逐张重建"砍成 O(n⁴) 的"增量松弛"。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 「固定一端 + 增量 Floyd」通用套路
// 场景:要对所有区间 [l, r] 的诱导子图做全源最短路
for (int l = 1; l <= n; l++) {
    // (1) 只把 [l, n] 的直连边放进矩阵
    for (int i = l; i <= n; i++)
        for (int j = l; j <= n; j++)
            d[i][j] = g[i][j];

    for (int r = l; r <= n; r++) {
        // (2) 用"新来的点 r"当中间点,在 [l, n] 上补一次松弛
        //     范围一定留到 n:后面还要用它去松弛更大的点
        for (int i = l; i <= n; i++) {
            if (d[i][r] >= INF) continue;
            for (int j = l; j <= n; j++)
                d[i][j] = min(d[i][j], d[i][r] + d[r][j]);
        }
        // (3) 此时 d 在 [l, r] 上就是 G(l, r) 的全源最短路
        //     需要统计什么就顺手统计什么
    }
}

// 复杂度:Σ_l (n − l)³ ≈ n⁴ / 4,而不是"逐张重建"的 n⁵
// 判断能否用增量:相邻两个状态是否只差"一个点 / 一条边 / 一个字符"

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
固定一端枚举把二维的 (ℓ, r) 变成"一维长大",中间点 k 复用所有"区间子图"类统计题
增量松弛新点只多一层中间点,老结果不丢动态加点(在线)最短路、Floyd 的在线版本
重边取最小用邻接矩阵天然合并重复边所有用矩阵存图的最短路题
不计不连通"不连通记 0"= 直接跳过该点对贡献统计类问题里的"不可达特判"
🌟
思考题:如果把子图定义改成"只删点不删边"(即 G(ℓ, r) 里仍保留跨出区间的边),增量法还能用吗?(提示:不行——那时 G(ℓ, r) 会通过区间外的点相连,"只差一个点"的性质消失了。增量法的前提是"局部性":新状态必须只比旧状态多一点点信息。)