最小边权和

GitHub跳转原题关系图返回列表

把边按边权升序排序后逐边做 DP 松弛,f[a][v][k] 表示从 a 出发走恰好 k 条非降权边到 v 的最小和,最后对 k 取前缀最小、询问 O(1)。

OJ: roj

题目 ID: 1721

难度:提高+/省选-

标签:动态规划图论最短路python

创建: 2026-10-07 18:33

更新: 2026-10-07 18:33

形式化题目

给定有向图 G=(V,E)G=(V,E),∣V∣=n|V| = n、∣E∣=m|E| = m,每条边 ee 带权 wew_e,且所有边权两两不同。 对于 qq 组询问 (a,b,c)(a, b, c),求

min⁡{∑i=1kwei  ∣  k⩽c,  a→e1v1→e2⋯→ekb,  we1⩽we2⩽⋯⩽wek}, \min\Big\{\sum_{i=1}^{k} w_{e_i} \;\Big|\; k \leqslant c,\; a \xrightarrow{e_1} v_1 \xrightarrow{e_2} \cdots \xrightarrow{e_k} b,\; w_{e_1} \leqslant w_{e_2} \leqslant \cdots \leqslant w_{e_k}\Big\},

即从 aa 走不超过 cc 条边到 bb、途中边权不下降的最小边权和;不存在这样的走路时输出 −1-1。 n⩽150n \leqslant 150,m⩽5000m \leqslant 5000,q⩽1000q \leqslant 1000,w⩽5000w \leqslant 5000。

几条从题面与数据里都能直接读出的边界约定:

  • a=ba = b 且 c⩾0c \geqslant 0 时答案为 00(走 00 条边,也算"不超过 cc 条");
  • cc 没有给出上界,实测数据里出现过 c=109c = 10^9,须按 64 位整数读入;
  • 边权为正,"去掉走路中的环"不会让和变大,所以最优解总能取成简单路径,长度不超过 n−1n-1。

正解

思路

朴素做法。 把"走路"当成状态:dp[v][last][k]\mathrm{dp}[v][\text{last}][k] 表示走到 vv、最后一条边权为 last\mathrm{last}、已用 kk 条边的最小和,转移时枚举所有边。状态里带边权这一维就爆了; 若退化成"以 vv 为起点跑一遍 Dijkstra 再检查路径是否单调",则单调性约束根本无法用最短路刻画。

关键观察:边权两两不同时,“不下降"等价于"按边权升序使用这些边”。 一条合法走路上 we1⩽⋯⩽wekw_{e_1} \leqslant \cdots \leqslant w_{e_k},而所有边权互不相同, 所以这条不等式链其实处处取严格不等号:走路上的边在"按 ww 升序排列的边表"里出现的 位置,与它在走路里出现的次序完全一致。 于是不需要在状态里记边权, 只要按边权升序把边一条一条"插进图里",插入顺序就自动等于行走顺序。

这给出了一个很像 Bellman–Ford 的过程。设

f[a][v][k]=从 a 出发、在已插入的边集中走**恰好** k 条边到达 v 的最小边权和, f[a][v][k] = \text{从 } a \text{ 出发、在已插入的边集中走**恰好** } k \text{ 条边到达 } v \text{ 的最小边权和},

初值 f[a][a][0]=0f[a][a][0] = 0,其余为 +∞+\infty。插入边 e=(u,v,w)e = (u, v, w) 时对每个起点 aa 做

f[a][v][k]  ←  min⁡(f[a][v][k],  f[a][u][k−1]+w),k=n,n−1,…,1. f[a][v][k] \;\leftarrow\; \min\big(f[a][v][k],\; f[a][u][k-1] + w\big), \qquad k = n, n-1, \dots, 1 .

kk 从大到小枚举是关键:读到 f[a][u][k−1]f[a][u][k-1] 时它还是"插入这条边之前"的旧值, 因此一条边在一次松弛里最多被用一次,kk 就精确等于走路用掉的边数。

为什么每条边只用松弛一次就够了? 因为合法走路的边一定互不相同:权严格递增即下标严格递增。 所以走路恰好被"按其最后一条边被插入的那一刻"完整枚举到——插入那条边时, f[a][u][⋅]f[a][u][\cdot] 里已经累好了这条走路的其余部分。

询问的收尾。 题目允许"不超过 cc 条",所以对每个 (a,v)(a, v) 把 kk 做前缀最小: f[a][v][k]←min⁡(f[a][v][k],f[a][v][k−1])f[a][v][k] \leftarrow \min(f[a][v][k], f[a][v][k-1]),之后 f[a][v][k]f[a][v][k] 的含义变成"不超过 kk 条边"。 询问即 O(1)O(1):c←min⁡(c,n)c \leftarrow \min(c, n)(简单路径长度 ⩽n−1\leqslant n-1, cc 超过 nn 的部分永远用不上),再查 f[a][b][c]f[a][b][c],被 +∞+\infty 污染过就输出 −1-1。

用题面样例验证一遍,其中起点固定为 a=1a = 1。9 条边按 ww 升序依次是 1→2(1)1{\to}2(1)、2→3(2)2{\to}3(2)、3→4(3)3{\to}4(3)、7→4(4)7{\to}4(4)、1→7(5)1{\to}7(5)、5→8(7)5{\to}8(7)、1→6(8)1{\to}6(8)、6→4(9)6{\to}4(9)、4→5(12)4{\to}5(12), 插入过程中 f[1][4][⋅]f[1][4][\cdot] 的变化是

插入的边(升序) 由此新得到的最优走路 f[1][4][1]f[1][4][1] f[1][4][2]f[1][4][2] f[1][4][3]f[1][4][3]
1→2  (1)1{\to}2\;(1) 1→2=11{\to}2 = 1 ∞\infty ∞\infty ∞\infty
2→3  (2)2{\to}3\;(2) 1→2→3=31{\to}2{\to}3 = 3 ∞\infty ∞\infty ∞\infty
3→4  (3)3{\to}4\;(3) 1→2→3→4=61{\to}2{\to}3{\to}4 = 6 ∞\infty ∞\infty 66
7→4  (4)7{\to}4\;(4) 点 77 尚不可达,无 ∞\infty ∞\infty 66
1→7  (5)1{\to}7\;(5) 1→7=51{\to}7 = 5 ∞\infty ∞\infty 66
5→8  (7)5{\to}8\;(7) 点 55 尚不可达,无 ∞\infty ∞\infty 66
1→6  (8)1{\to}6\;(8) 1→6=81{\to}6 = 8 ∞\infty ∞\infty 66
6→4  (9)6{\to}4\;(9) 1→6→4=171{\to}6{\to}4 = 17 ∞\infty 1717 66
4→5  (12)4{\to}5\;(12) 1→2→3→4→5=181{\to}2{\to}3{\to}4{\to}5 = 18(终点是 55,不影响上表三列) ∞\infty 1717 66

于是 c=2c=2 时答案 1717、c=3c=3 时答案 66、c=1c=1 时 −1-1,与样例一致。 表中"c=2c=2 的答案为什么不是 1→7→4=91{\to}7{\to}4 = 9"也一目了然:那条走路的边权是 5,45, 4, 5>45 > 4 违反不下降,DP 根本不会把它记进 f[1][4][2]f[1][4][2]—— f[1][4][2]f[1][4][2] 只能由"边 7→4(4)7{\to}4(4) 在边 1→7(5)1{\to}7(5) 之后被插入"产生, 而插入顺序是按权升序,7→47{\to}4 排在 1→71{\to}7 前面,串不起来。

下图画出上述"按权升序插边"的骨架:每插一条边,就把它当作走路的最后一步接上去。

flowchart TD
    E1["插入 1→2 (w=1)"] --> E2["插入 2→3 (w=2)"]
    E2 --> E3["插入 3→4 (w=3)<br/>得到 1→2→3→4 = 6"]
    E3 --> E4["插入 7→4 (w=4)"]
    E4 --> E5["插入 1→7 (w=5)"]
    E5 --> E6["插入 1→6 (w=8)"]
    E6 --> E7["插入 6→4 (w=9)<br/>得到 1→6→4 = 17"]
    E7 --> Q["前缀 min 后询问 O(1)<br/>c=2→17, c=3→6, c=1→-1"]

两个容易写错的坑。

  1. kk 的枚举方向:正着枚举 kk,f[a][u][k−1]f[a][u][k-1] 可能已经在本轮被这条边更新过, 一条边就会被反复使用(f[a][v][k+1]=f[a][v][k]+wf[a][v][k+1] = f[a][v][k] + w 这种"套娃"),答案会被低估。
  2. cc 的截断与类型:cc 可以到 10910^9,必须用 long long / Python 大整数读入; 截断成 min⁡(c,n)\min(c, n) 才敢拿它当数组下标。

代码

Python 版:

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 18:33
# update_at: 2026-10-07 18:33

import sys
from itertools import accumulate
from operator import itemgetter

INF = 1 << 30  # 不可达标记;真实答案 <= 149 * 5000 = 745000,被它污染过的格只会更大
JUNK = 10 ** 8  # 一格超过它就说明从没被真正走到过,该询问无解输出 -1

# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type Edge = tuple[int, int, int]  # (u, v, w) 一条有向边
type Table = dict[int, list[list[int]]]  # F[a][v][k]:从 a 走恰好 k 条边到 v 的最小边权和
type StepCap = dict[int, int]  # 起点 a -> 它被问到的最大边数(已夹到 [0, n])


def build_table(edges: list[Edge], cap: StepCap, n: int) -> Table:
    """按边权升序逐边松弛,算出每个询问起点的 F[a][v][k],k 上限只取该起点真正会问到的 cap[a]。"""
    F: Table = {a: [[INF] * (cap[a] + 1) for _ in range(n + 1)] for a in cap}
    for a in cap:
        F[a][a][0] = 0  # 走 0 条边:自己到自己,代价 0
    for u, v, w in edges:  # 边已按 w 升序排好,这个处理顺序就是行走时边的使用顺序
        for fa in F.values():
            dst, src = fa[v], fa[u]
            # 整段 k 交给 map / 推导式在 C 层跑:右侧按旧值算完再整体写回,
            # 等价于"所有 k 同时更新",所以同一次松弛里这条边不会被用上两回。
            dst[1:] = list(map(min, dst[1:], [x + w for x in src[:-1]]))
    return F


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m, q = next(data), next(data), next(data)
    edges: list[Edge] = [(next(data), next(data), next(data)) for _ in range(m)]
    queries: list[Edge] = [(next(data), next(data), next(data)) for _ in range(q)]
    edges.sort(key=itemgetter(2))  # 按 w 升序;题面保证 w 两两不同,排序顺序即行走顺序

    # 边数上限统一夹到 [0, n]:正权下最优解一定是简单路径,长度不超过 n-1;
    # c 没给上界(数据里到 1e9),也可能取 0,负数按不可走处理。
    steps: list[int] = [max(0, min(c, n)) for _, _, c in queries]
    cap: StepCap = {}
    for (a, _, _), step in zip(queries, steps):
        cap[a] = max(cap.get(a, 0), step)

    F = build_table(edges, cap, n)

    # 只有被问到的 (起点, 终点) 行要把"恰好 k 条边"改成"不超过 k 条边":
    # 累计最小值一次成型,代替再扫一遍 k。
    asked = {(a, b) for a, b, _ in queries}
    best = {pair: list(accumulate(F[pair[0]][pair[1]], min)) for pair in asked}

    ans: list[str] = []
    for (a, b, _), step in zip(queries, steps):
        cost = best[a, b][step]
        ans.append(str(cost) if cost <= JUNK else "-1")
    print("\n".join(ans))


if __name__ == "__main__":
    solve()

C++ 版(同一算法):

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 18:33
 * update_at: 2026-10-07 18:33
 */
// main.cpp:最小边权和。把边按 w 升序排序,逐边做 DP 松弛:
// f[a][v][k] = 从点 a 出发、恰好走 k 条边、边权非降序到达点 v 的最小边权和。
// 排序后的处理顺序就是"边权非降序"时边的使用顺序,所以每条边只需松弛一次。

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

typedef long long ll;

const int MAXN = 150;       // 点数上界
const int MAXM = 5000;      // 边数上界
const int INF = 0x3f3f3f3f; // 不可达标记;真实答案 <= 149 * 5000 = 745000,远小于它
const int JUNK = 100000000; // 超过它说明该格被 INF 污染过,判无解输出 -1

struct Edge {
    int u; // 起点
    int v; // 终点
    int w; // 边权(题面保证两两不同,单个不超过 5000,int 够用)
};
Edge e[MAXM]; // 读入后按 w 升序重排

// f[a][v][k] 用 int 存:真实答案上界 745000 与 INF = 0x3f3f3f3f 不会混淆,
// 用 int 把 150^3 个状态压到约 14 MB(换成 ll 会翻倍)。
// 语义随状态推进变化:松弛阶段是"恰好 k 条边",做完前缀 min 后变成"不超过 k 条边"。
int f[MAXN + 1][MAXN + 1][MAXN + 1];

// 按边权升序排序:题面保证 w 两两不同,所以这个顺序唯一,就是行走时边的使用顺序
bool cmp_edge(const Edge &x, const Edge &y) {
    return x.w < y.w;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, m, q;
    cin >> n >> m >> q;

    for (ll i = 0; i < m; i++) {
        cin >> e[i].u >> e[i].v >> e[i].w;
    }
    sort(e, e + m, cmp_edge);

    memset(f, 0x3f, sizeof(f)); // 全部先标成不可达
    for (ll a = 1; a <= n; a++) {
        f[a][a][0] = 0; // 走 0 条边:自己到自己,代价 0
    }

    // 逐边松弛。k 从大到小枚举,保证读到的是"这条边松弛之前"的 f[a][u][k-1],
    // 于是一条边在一次松弛里不会被重复使用,k 与走路实际用掉的边数严格对应。
    for (ll t = 0; t < m; t++) {
        ll u = e[t].u;
        ll v = e[t].v;
        ll w = e[t].w;
        for (ll a = 1; a <= n; a++) {
            for (ll k = n; k >= 1; k--) {
                int cand = f[a][u][k - 1] + w;
                if (cand < f[a][v][k]) {
                    f[a][v][k] = cand;
                }
            }
        }
    }

    // 前缀 min:把"恰好 k 条边"改成"不超过 k 条边",因为询问允许少走几条边
    for (ll a = 1; a <= n; a++) {
        for (ll b = 1; b <= n; b++) {
            for (ll k = 1; k <= n; k++) {
                if (f[a][b][k - 1] < f[a][b][k]) {
                    f[a][b][k] = f[a][b][k - 1];
                }
            }
        }
    }

    for (ll t = 0; t < q; t++) {
        ll a, b, c;
        cin >> a >> b >> c;
        // 最优解一定是简单路径(去掉环代价严格变小),长度不超过 n-1,
        // 所以 c 超过 n 时截断不影响答案;c 没有给上界,数据里出现过 1e9,用 ll 读入。
        if (c > n) c = n;
        if (c < 0) c = 0;
        ll ans = f[a][b][c]; // 此处 c 已夹在 [0, n]
        if (ans > JUNK) {
            cout << -1 << "\n";
        } else {
            cout << ans << "\n";
        }
    }

    return 0;
}

复杂度

  • 时间:预处理 O(mlog⁡m)O(m \log m) 排序,然后每条边对每个起点做一次 O(n)O(n) 的 kk 维松弛, 共 O(mn2)O(m n^2);询问 O(1)O(1)。代入上界 5000×1502≈1.1×1085000 \times 150^2 \approx 1.1\times 10^8, C++ 实测最慢测点(n=150,m=5000,q=1000n=150, m=5000, q=1000)0.14 s(限时 1000 ms)。
  • 空间:ff 有 (n+1)3≈3.4×106(n+1)^3 \approx 3.4\times 10^6 个状态, 用 int 存约 14 MB(答案上界 149×5000=745000149 \times 5000 = 745000 远小于 INF = 0x3f3f3f3f, 不会与不可达标记混淆,所以不必开 long long),实测峰值 15.5 MB。
  • Python 侧:算法与 C++ 同阶(同样是 O(mn2)O(mn^2) 的松弛,只是把 kk 这一维交给 map / 推导式在 C 层跑),但常数大:最大测点约 5.7 s,会超过 1 s 限时—— 属于允许的 Python TLE,算法本身没有降级;小数据(m⩽3000m \leqslant 3000)与样例都在 2.4 s 内。

总结

  • 不下降 + 边权互不相同 = 排序后逐边插入。 这是本题的全部出口: 把"路径上的约束"换位成"处理顺序上的约束",状态里那一维边权就消失了。
  • 插入顺序即行走顺序,所以每条边只需松弛一次。 注意这里**“边权两两不同”是承重的前提**: 若两条同权边需要串接(如 1→21{\to}2、2→32{\to}3 同为 55,再问 1→3,c⩾21 \to 3, c \geqslant 2), 写在同一轮的松弛就会错过它们——必须对同权边的整组做多轮松弛(分层图上的 Bellman–Ford, 见素材源 std.cpp 的加固写法)才能处理。本题题面保证权值互不相同,所以单轮足够; 本文的 main.cpp / main.py 都只写单轮,与题面一致。
  • “恰好 kk 条” → “O(1)O(1) 询问”:kk 维从大到小松弛保证每条边只用一次, 最后对它取前缀最小就换成"不超过 kk 条",qq 组询问不再需要任何额外计算。
  • 正权 + 简单路径:由"去环不增代价"得到长度上界 n−1n-1,于是 c⩾nc \geqslant n 时截断到 nn, 既省时间又避免 cc 过大时下标越界。
  • 本题素材的可靠性说明:随仓 data/ 带 data.py 生成脚本,属于按题面自造的测试数据 (data.py 里逐点写明了规模与意图),题面本身是网络重建(素材源 std.cpp 的注释给出了 若干 CSDN 题解出处),因此“出题人的原始意图”与官方原题可能存在细节偏差。 可以核实的是:10 个测点里每条边的 ww 确实都两两不同,与题面一致。 本文的结论均以题面与随仓数据为准,并已用 main.cpp 与 main.py 两个实现独立跑通全部 10 个测点。

图示解析

插边顺序如何决定可行性

下图不是图结构,而是一条处理时间线:9 个节点就是 9 条边,箭头表示"先插哪条、后插哪条"。 一条合法走路必须在时间线上从左往右挑边,且挑出的边首尾相接。

flowchart LR
    P1["① 1→2 w=1"] --> P2["② 2→3 w=2"] --> P3["③ 3→4 w=3"]
    P3 --> P4["④ 7→4 w=4"] --> P5["⑤ 1→7 w=5"] --> P6["⑥ 5→8 w=7"]
    P6 --> P7["⑦ 1→6 w=8"] --> P8["⑧ 6→4 w=9"] --> P9["⑨ 4→5 w=12"]
  • 1→2→3→41{\to}2{\to}3{\to}4(权和 66)用到的 ①②③ 在时间线上依次出现且首尾相接,所以合法; 它的长度是 33,因此 c=2c = 2 时凑不出来。
  • 5+4=95+4 = 9 那条 1→7→41{\to}7{\to}4 表面更短,但 1→71{\to}7 是 ⑤、7→47{\to}4 是 ④, 在时间线上反序,拼不出非降权走路——这正是本题与普通最短路的分水岭。
  • 1→6→41{\to}6{\to}4 用到 ⑦⑧,在时间线上顺序且相接,于是它是 c=2c = 2 时唯一可行的路,答案 1717。