把边按边权升序排序后逐边做 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
形式化题目
给定有向图
即从
几条从题面与数据里都能直接读出的边界约定:
且 时答案为 (走 条边,也算"不超过 条"); 没有给出上界,实测数据里出现过 ,须按 64 位整数读入; - 边权为正,"去掉走路中的环"不会让和变大,所以最优解总能取成简单路径,长度不超过
。
正解
思路
朴素做法。 把"走路"当成状态:
关键观察:边权两两不同时,“不下降"等价于"按边权升序使用这些边”。
一条合法走路上
这给出了一个很像 Bellman–Ford 的过程。设
初值
为什么每条边只用松弛一次就够了? 因为合法走路的边一定互不相同:权严格递增即下标严格递增。
所以走路恰好被"按其最后一条边被插入的那一刻"完整枚举到——插入那条边时,
询问的收尾。 题目允许"不超过
用题面样例验证一遍,其中起点固定为
| 插入的边(升序) | 由此新得到的最优走路 | |||
|---|---|---|---|---|
| 点 |
||||
| 点 |
||||
于是
下图画出上述"按权升序插边"的骨架:每插一条边,就把它当作走路的最后一步接上去。
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"]
两个容易写错的坑。
的枚举方向:正着枚举 , 可能已经在本轮被这条边更新过, 一条边就会被反复使用( 这种"套娃"),答案会被低估。 的截断与类型: 可以到 ,必须用 long long/ 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++ 版(同一算法):
/**
* 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;
}复杂度
- 时间:预处理
排序,然后每条边对每个起点做一次 的 维松弛, 共 ;询问 。代入上界 , C++ 实测最慢测点( )0.14 s(限时 1000 ms)。 - 空间:
有 个状态, 用 int存约 14 MB(答案上界远小于 INF = 0x3f3f3f3f, 不会与不可达标记混淆,所以不必开long long),实测峰值 15.5 MB。 - Python 侧:算法与 C++ 同阶(同样是
的松弛,只是把 这一维交给 map/ 推导式在 C 层跑),但常数大:最大测点约 5.7 s,会超过 1 s 限时—— 属于允许的 Python TLE,算法本身没有降级;小数据()与样例都在 2.4 s 内。
总结
- 不下降 + 边权互不相同 = 排序后逐边插入。 这是本题的全部出口: 把"路径上的约束"换位成"处理顺序上的约束",状态里那一维边权就消失了。
- 插入顺序即行走顺序,所以每条边只需松弛一次。 注意这里**“边权两两不同”是承重的前提**:
若两条同权边需要串接(如
、 同为 ,再问 ), 写在同一轮的松弛就会错过它们——必须对同权边的整组做多轮松弛(分层图上的 Bellman–Ford, 见素材源 std.cpp的加固写法)才能处理。本题题面保证权值互不相同,所以单轮足够; 本文的main.cpp/main.py都只写单轮,与题面一致。 - “恰好
条” → “ 询问”: 维从大到小松弛保证每条边只用一次, 最后对它取前缀最小就换成"不超过 条", 组询问不再需要任何额外计算。 - 正权 + 简单路径:由"去环不增代价"得到长度上界
,于是 时截断到 , 既省时间又避免 过大时下标越界。 - 本题素材的可靠性说明:随仓
data/带data.py生成脚本,属于按题面自造的测试数据 (data.py里逐点写明了规模与意图),题面本身是网络重建(素材源std.cpp的注释给出了 若干 CSDN 题解出处),因此“出题人的原始意图”与官方原题可能存在细节偏差。 可以核实的是:10 个测点里每条边的确实都两两不同,与题面一致。 本文的结论均以题面与随仓数据为准,并已用 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"]
(权和 )用到的 ①②③ 在时间线上依次出现且首尾相接,所以合法; 它的长度是 ,因此 时凑不出来。 那条 表面更短,但 是 ⑤、 是 ④, 在时间线上反序,拼不出非降权走路——这正是本题与普通最短路的分水岭。 用到 ⑦⑧,在时间线上顺序且相接,于是它是 时唯一可行的路,答案 。