每条路径的耗时是拥堵系数 a 的直线,期望最短路即这些直线的下包络在 [0,1] 上的积分;用凹函数中点弦值判定递归细分,分段梯形积分。
OJ: roj
题目 ID: 1723
难度:提高+/省选-
标签:图论最短路积分分治python
创建: 2026-10-07 18:43
更新: 2026-10-07 18:43
形式化题目
给一张
全市的拥堵系数
固定
输出一行一个实数。题面未规定小数位数,样例输出为 2.5、13.0(保留一位小数的形式),
故本题按去尾零方式输出:打印足够位小数后删掉多余尾零,至少保留一位小数,
这样既与样例逐字符一致,又保留了
正解
思路
朴素想法与它的难点。 最直白的做法是把
第一个观察:路径代价是
即斜率
是有限族直线的下包络。下包络的两个基本事实直接决定了整道题的做法:
- 凸性/凹性:有限个仿射函数的下包络必然是凹函数(下包络
任何一条直线, 而取到最小值处是凸组合)。所以 在 上凹、连续、分段线性。 - 折点有限:折点只会出现在两条直线的交点处,数目不超过直线条数。
第二个观察:凹函数的一个可判定性质。
设
理由是一行凸组合:凹性给出
算法。 对区间
- 若
:认定整段是该弦,直接累加梯形面积 ; - 否则区间内存在折点,递归处理
与 。
初始调用是
为什么精度可控。 斜率
附:样例 2 手算核对。 用精确有理数算样例 2 的
| 15 | 14 | 13 | 12 | 11 |
四点连成一条直线,梯形积分得 13.0 完全一致;
另一组样例 2.5 一致。两个样例互相印证了算法与输出格式。
重边与自环。 重边天然被 Dijkstra 处理(平行边就是多条平行直线,下包络自动取舍;
数据点 9 特意造了 300 条
代码
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:43
# update_at: 2026-10-07 18:43
import sys
from heapq import heappop, heappush
INF = float("inf")
EPS_ABS = 1e-8 # 弦值比较的绝对容差,扛小量级距离上的浮点噪声
EPS_REL = 1e-11 # 相对容差,按距离量级放大(沿 <=200 条边累加,误差远小于它)
MAX_DEPTH = 50 # 细分深度上限,防止在浮点噪声处无限二分
type Adj = list[list[tuple[int, int, int]]] # adj[u] = [(v, x, y)],无向边两侧各存一份
def shortest(a: float, adj: Adj, s: int, t: int) -> float:
"""拥堵系数固定为 a 时 s->t 的最短路(堆优化 Dijkstra)。"""
dist = {s: 0.0}
heap = [(0.0, s)]
while heap:
d, u = heappop(heap)
if u == t:
return d # 终点出堆时距离已确定
if d > dist.get(u, INF):
continue # 堆里的过时记录
for v, x, y in adj[u]:
nd = d + a * x + (1.0 - a) * y
if nd < dist.get(v, INF):
dist[v] = nd
heappush(heap, (nd, v))
return dist.get(t, INF)
def integrate(lo: float, hi: float, flo: float, fhi: float,
adj: Adj, s: int, t: int, depth: int = 0) -> float:
"""在 [lo,hi] 上积分 d(a),已知两端值 flo=d(lo)、fhi=d(hi)。
d(a) 是若干直线(每条路径代价 = Y_P + a*(X_P-Y_P))的下包络,故在 [0,1] 上凹且
分段线性。凹函数在区间中点的值一旦等于两端弦值,整段就贴合这条弦,可以直接按
梯形算面积;否则区间内还有折点,二分继续细分。斜率是整数,折点两侧斜率差至少 1,
每次细分间隙减半,所以深度有限(再用 MAX_DEPTH 兜底)。
"""
mid = (lo + hi) * 0.5
fm = shortest(mid, adj, s, t)
chord = (flo + fhi) * 0.5 # 两端点连线在中点的高度
eps = EPS_ABS + EPS_REL * max(abs(flo), abs(fhi), 1.0)
if depth >= MAX_DEPTH or fm <= chord + eps:
return chord * (hi - lo) # 该段就是直线,梯形面积即精确值
return (integrate(lo, mid, flo, fm, adj, s, t, depth + 1)
+ integrate(mid, hi, fm, fhi, adj, s, t, depth + 1))
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n, m, s, t = next(data), next(data), next(data), next(data)
adj: Adj = [[] for _ in range(n + 1)]
for _ in range(m):
u, v, x, y = next(data), next(data), next(data), next(data)
adj[u].append((v, x, y)) # 无向边:两个方向都放
adj[v].append((u, x, y))
f0 = shortest(0.0, adj, s, t) # a=0:每条边取空闲耗时 y
f1 = shortest(1.0, adj, s, t) # a=1:每条边取最拥堵耗时 x
ans = integrate(0.0, 1.0, f0, f1, adj, s, t)
# 题面没规定精度,样例是 "2.5" / "13.0":打印 10 位小数后去掉多余尾零(至少留一位)
text = f"{ans:.10f}".rstrip("0")
print(text + "0" if text.endswith(".") else text)
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:43
* update_at: 2026-10-07 18:43
*/
// 一本通 1723《交通》:期望意义下的最短路。
// 拥堵系数 a ~ U[0,1],边 e 在 a 下的耗时 w_e(a) = a*x_e + (1-a)*y_e,
// 求 ∫_0^1 d(a) da,其中 d(a) 是 a 固定时 S->T 的最短路。
//
// 关键性质:一条路径 P 的代价是 a 的直线 cost_P(a) = Y_P + a*(X_P - Y_P)
// (X_P = Σx_e,Y_P = Σy_e),d(a) 是这些直线的下包络,因此 d(a) 在 [0,1] 上
// 凹且分段线性。凹函数在区间中点的函数值若等于两端点的弦值,则该区间上 d 就是
// 这条弦(凹函数在区间内一旦低于弦,中点必然被凸组合抬高),于是可以递归细分:
// 中点弦值相等就整段按梯形积分,否则说明区间内还有折点,二分继续。
// 直线斜率 X_P - Y_P 是整数,折点很少,实际只做几百次 Dijkstra。
//
// 来源说明:本题素材源带自造数据生成脚本,题面为网络重建版本,与官方原题可能有偏差;
// 随仓 std.cpp 只作算法参考,本文件按题面独立重写(链式前向星 + 同样的细分判定)。
#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;
typedef long long ll;
const int MAXN = 205; // 顶点数上限(题面 n <= 200)
const int MAXM = 810; // 有向边数上限(题面双向边 m <= 400,成对存)
const double INF = 1e300; // 不可达的哨兵距离
struct Edge {
int to; // 边指向的点
double x; // 最拥堵时的耗时
double y; // 完全空闲时的耗时
};
Edge edge[MAXM]; // 链式前向星:所有有向边
int head[MAXN]; // head[u] 是 u 的第一条出边编号,0 表示没有
int nxt[MAXM]; // nxt[i] 是 i 的下一条同起点边编号
int edge_cnt; // 已加入的有向边条数
int n, m, S, T; // 点数、双向边数、起点、终点
double dist_arr[MAXN]; // 固定 a 时的单源最短路长度
// 加一条 u->v 的有向边
void add_edge(int u, int v, double x, double y) {
edge_cnt++;
edge[edge_cnt].to = v;
edge[edge_cnt].x = x;
edge[edge_cnt].y = y;
nxt[edge_cnt] = head[u];
head[u] = edge_cnt;
}
// 拥堵系数为 a 时从 S 到 T 的最短路(堆优化 Dijkstra),返回 dist[T]
double shortest_path(double a) {
typedef pair<double, int> Node;
priority_queue<Node, vector<Node>, greater<Node> > pq;
for (int i = 1; i <= n; ++i) dist_arr[i] = INF;
dist_arr[S] = 0.0;
pq.push(Node(0.0, S));
while (!pq.empty()) {
Node top = pq.top();
pq.pop();
int u = top.second;
double d = top.first;
if (u == T) return d; // 终点出堆时距离已确定
if (d > dist_arr[u]) continue; // 堆里的过时记录
for (int i = head[u]; i; i = nxt[i]) {
double w = a * edge[i].x + (1.0 - a) * edge[i].y;
double nd = d + w;
if (nd < dist_arr[edge[i].to]) {
dist_arr[edge[i].to] = nd;
pq.push(Node(nd, edge[i].to));
}
}
}
return dist_arr[T];
}
// 在 [lo,hi] 上积分 d(a),已知 flo = d(lo)、fhi = d(hi)
double integrate(double lo, double hi, double flo, double fhi, int depth) {
double mid = (lo + hi) * 0.5;
double fm = shortest_path(mid);
double chord = (flo + fhi) * 0.5; // 两端点连线在中点的高度
// 容差:绝对项扛小量级噪声,相对项按距离量级放大
// (Dijkstra 沿不超过 n 条边累加,相对舍入误差不超过 n*2^-52 量级)
double scale = flo > fhi ? flo : fhi;
if (scale < 1.0) scale = 1.0;
double eps = 1e-8 + 1e-11 * scale;
if (depth >= 50 || fm <= chord + eps) return chord * (hi - lo);
return integrate(lo, mid, flo, fm, depth + 1) +
integrate(mid, hi, fm, fhi, depth + 1);
}
int main() {
if (scanf("%d %d %d %d", &n, &m, &S, &T) != 4) return 0;
for (int i = 1; i <= m; ++i) {
int u, v;
double x, y;
scanf("%d %d %lf %lf", &u, &v, &x, &y);
add_edge(u, v, x, y);
add_edge(v, u, x, y);
}
double f0 = shortest_path(0.0); // a=0 时每条边取空闲耗时 y
double f1 = shortest_path(1.0); // a=1 时每条边取最拥堵耗时 x
double ans = integrate(0.0, 1.0, f0, f1, 0);
// 输出:题面未规定精度,样例是 "2.5" / "13.0"。按 10 位小数打印后去掉多余
// 尾零(至少保留一位小数),既与样例逐字符一致,又保留足够有效位。
char buf[64];
snprintf(buf, sizeof(buf), "%.10f", ans);
int dot = -1, last = 0;
for (int i = 0; buf[i]; ++i) {
if (buf[i] == '.') dot = i;
last = i;
}
if (dot >= 0) {
while (last > dot + 1 && buf[last] == '0') {
buf[last] = '\0';
last--;
}
}
printf("%s\n", buf);
return 0;
}复杂度
- 时间:一次 Dijkstra 是
;细分次数由折点数与容差决定, 实测随机数据下 Dijkstra 调用次数在几百次量级(最坏结构是数据点 9 的 300 条平行边), 总复杂度 , 在 、 下毫秒级。 - 空间:链式前向星
,Dijkstra 的堆与距离数组 ,递归深度不超过 , 合计 。Python 版用迭代栈代替递归,同样 。 - 与 C++ 解法的关系:两者是同一次递归细分,
main.cpp用链式前向星加priority_queue,main.py用adj[u]列表加heapq;Python 把递归改写成显式栈, 并把"是否细分"的判定写成同一个不等式。算法同阶,Python 常数更大, 本题规模下仍有充足余量(允许 Python TLE,但绝不因此换成暴力的离散采样)。
总结
- “期望最短路"不是"最短路取期望”:期望要加在积分外面,
。前者是折线的面积,后者才是直线的交点值, 这两者的差别正是本题的全部难度。 - 先找结构,再想算法:路径代价是
的直线 是下包络 凹且分段线性。把"求积分"转化为"找折点",问题就成了可判定、可细分的形状。 - 凹函数的中点判定是一个便宜好用的武器:只需一次函数求值, 就能确认"这段是直线",从而用梯形面积精确积分,误差只来自浮点而非离散化。
- 容差要写成"绝对
相对"两项:绝对项扛小量级噪声,相对项随距离量级放大, 才能在答案高达 的数据上既不误判又不过度细分。 - 输出格式属于答案的一部分:题面只写"一行一个实数",样例却是
2.5/13.0这种去尾零的写法,因此按去尾零输出(至少留一位小数)是对齐判题数据最稳的选择。 - 来源说明:本题素材源目录里带自造数据的生成脚本(
data.py), 说明随仓data/是按题面重建的、并非官方数据;题面本身也是网络重建版本, 与一本通官方原题可能处于描述口径上的偏差。随仓std.cpp的算法思路与本文一致, 已用真实数据逐点核对通过,故作为参考保留,未逐行照抄。