交通

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

每条路径的耗时是拥堵系数 a 的直线,期望最短路即这些直线的下包络在 [0,1] 上的积分;用凹函数中点弦值判定递归细分,分段梯形积分。

OJ: roj

题目 ID: 1723

难度:提高+/省选-

标签:图论最短路积分分治python

创建: 2026-10-07 18:43

更新: 2026-10-07 18:43

形式化题目

给一张 nn 个点、mm 条无向边的图(可有重边、无自环,点从 11 编号)。每条边 ee 带 两个参数 xex_e(最拥堵时的耗时)与 yey_e(完全空闲时的耗时),1⩽xe,ye⩽1071 \leqslant x_e, y_e \leqslant 10^7 (题面明说 xex_e 可能小于 yey_e,不保证 x⩾yx \geqslant y)。

全市的拥堵系数 aa 在 [0,1][0,1] 上均匀随机,aa 下边 ee 的耗时是它的一次函数

we(a)=a xe+(1−a) ye=ye+a (xe−ye).w_e(a) = a\,x_e + (1-a)\,y_e = y_e + a\,(x_e - y_e).

固定 aa 时,令 d(a)d(a) 为 SS 到 TT 的最短路长度(SS 到 TT 保证连通)。求期望

ans=Ea[d(a)]=∫01d(a) da.\mathrm{ans} = \mathbb{E}_a[d(a)] = \int_0^1 d(a)\,\mathrm{d}a .

输出一行一个实数。题面未规定小数位数,样例输出为 2.5、13.0(保留一位小数的形式), 故本题按去尾零方式输出:打印足够位小数后删掉多余尾零,至少保留一位小数, 这样既与样例逐字符一致,又保留了 10710^7 量级答案所需的有效位。

正解

思路

朴素想法与它的难点。 最直白的做法是把 aa 离散化成 KK 等份,对每个取值跑一次 Dijkstra 再求梯形和。这对光滑函数是可行的,但 d(a)d(a) 是折线:不同 aa 区间的最短路 可能走完全不同的路径,采样点落在折点两侧就会产生 O(步长⋅斜率差)O(\text{步长} \cdot \text{斜率差}) 的系统性误差。要保证 10−910^{-9} 级精度,需要 KK 大到不可接受,而且折点位置与数量都不已知。 真正的出路是找出折点,而不是加密采样。

第一个观察:路径代价是 aa 的直线。 一条 S→TS \to T 路径 PP 的总代价为

costP(a)=∑e∈P(ye+a(xe−ye))=∑e∈Pye⏟YP+a ∑e∈P(xe−ye)⏟XP−YP, \mathrm{cost}_P(a) = \sum_{e \in P} \bigl(y_e + a(x_e - y_e)\bigr) = \underbrace{\sum_{e \in P} y_e}_{Y_P} + a\,\underbrace{\sum_{e \in P} (x_e - y_e)}_{X_P - Y_P},

即斜率 sP=XP−YPs_P = X_P - Y_P、截距 YPY_P 的直线。于是

d(a)=min⁡PcostP(a)d(a) = \min_{P} \mathrm{cost}_P(a)

是有限族直线的下包络。下包络的两个基本事实直接决定了整道题的做法:

  1. 凸性/凹性:有限个仿射函数的下包络必然是凹函数(下包络 ⩽\leqslant 任何一条直线, 而取到最小值处是凸组合)。所以 dd 在 [0,1][0,1] 上凹、连续、分段线性。
  2. 折点有限:折点只会出现在两条直线的交点处,数目不超过直线条数。

第二个观察:凹函数的一个可判定性质。 设 ff 在 [l,r][l,r] 上凹,m=(l+r)/2m = (l+r)/2,弦值 chord=(f(l)+f(r))/2\mathrm{chord} = (f(l)+f(r))/2。 若 f(m)=chordf(m) = \mathrm{chord},则 ff 在整个 [l,r][l,r] 上恒等于这条弦。

理由是一行凸组合:凹性给出 f(m)⩾chordf(m) \geqslant \mathrm{chord};若严格大于,说明中点被"抬高", 区间内必有折点;反之 f(m)=chordf(m) = \mathrm{chord} 时,取任意点 p∈(l,m)p \in (l,m), 用凹性配合左右两端点作两重凸组合可以逼出 $f(p) = $ 弦值,逐点推进即得整段贴合。 这给出一个只靠一次函数求值就能完成的"这段是不是直线"判定——不需要知道折点在哪, 也不需要导数或斜率信息。

算法。 对区间 [l,r][l,r](已知 f(l)f(l)、f(r)f(r)),在中点跑一次 Dijkstra 得 f(m)f(m):

  • 若 f(m)⩽chord+εf(m) \leqslant \mathrm{chord} + \varepsilon:认定整段是该弦,直接累加梯形面积 chord⋅(r−l)\mathrm{chord} \cdot (r - l);
  • 否则区间内存在折点,递归处理 [l,m][l,m] 与 [m,r][m,r]。

初始调用是 [0,1][0,1],f(0)f(0) 与 f(1)f(1) 各跑一次 Dijkstra 得到(a=0a=0 时每条边取 yey_e, a=1a=1 时取 xex_e)。递归树只在含折点的区间上分叉, Dijkstra 的调用次数是 O(#折点⋅log⁡(1/ε))O(\#\text{折点} \cdot \log(1/\varepsilon)) 级别。

为什么精度可控。 斜率 sP=XP−YPs_P = X_P - Y_P 是整数(∣sP∣⩽200⋅107|s_P| \leqslant 200 \cdot 10^7), 折点两侧的斜率差至少是 11;在中点附近,两条直线的间隙约为 Δs⋅区间宽度/4\Delta s \cdot \text{区间宽度}/4,所以每次细分都会把间隙减半,用绝对容差 ε=10−8+10−11⋅max⁡(f(l),f(r),1)\varepsilon = 10^{-8} + 10^{-11} \cdot \max(f(l), f(r), 1) 判定, 配合最大深度 5050 双重保险,既不会被浮点噪声骗成"是直线", 也不会在折点处无限细分。容差里的相对项按距离量级放大: Dijkstra 沿不超过 n=200n = 200 条边累加,相对舍入误差不超过 n⋅2−52≈5×10−14n \cdot 2^{-52} \approx 5 \times 10^{-14},远小于 10−1110^{-11}。

附:样例 2 手算核对。 用精确有理数算样例 2 的 d(a)d(a):

aa 00 1/41/4 1/21/2 3/43/4 11
d(a)d(a) 15 14 13 12 11

四点连成一条直线,梯形积分得 ∫01d=13\int_0^1 d = 13,与题面 13.0 完全一致; 另一组样例 n=2, m=1n=2,\ m=1 只有一条边 x=3, y=2x=3,\ y=2,w(a)=2+aw(a) = 2 + a 恒为正 ⇒\Rightarrow 积分 =2.5= 2.5,与 2.5 一致。两个样例互相印证了算法与输出格式。

重边与自环。 重边天然被 Dijkstra 处理(平行边就是多条平行直线,下包络自动取舍; 数据点 9 特意造了 300 条 11–22 平行边,是最多折点的结构)。 题面保证无自环,代码也不依赖这一点。

代码

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: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++ 版(同一算法):

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: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 是 O(mlog⁡n)O(m \log n);细分次数由折点数与容差决定, 实测随机数据下 Dijkstra 调用次数在几百次量级(最坏结构是数据点 9 的 300 条平行边), 总复杂度 O(#折点log⁡(1/ε)⋅mlog⁡n)O(\#\text{折点} \log(1/\varepsilon) \cdot m \log n), 在 n⩽200n \leqslant 200、m⩽400m \leqslant 400 下毫秒级。
  • 空间:链式前向星 O(n+m)O(n + m),Dijkstra 的堆与距离数组 O(n)O(n),递归深度不超过 5050, 合计 O(n+m)O(n + m)。Python 版用迭代栈代替递归,同样 O(n+m)O(n + m)。
  • 与 C++ 解法的关系:两者是同一次递归细分,main.cpp 用链式前向星加 priority_queue,main.py 用 adj[u] 列表加 heapq;Python 把递归改写成显式栈, 并把"是否细分"的判定写成同一个不等式。算法同阶,Python 常数更大, 本题规模下仍有充足余量(允许 Python TLE,但绝不因此换成暴力的离散采样)。

总结

  • “期望最短路"不是"最短路取期望”:期望要加在积分外面, ∫min⁡P(⋯ )≠min⁡P∫(⋯ )\int \min_P (\cdots) \neq \min_P \int (\cdots)。前者是折线的面积,后者才是直线的交点值, 这两者的差别正是本题的全部难度。
  • 先找结构,再想算法:路径代价是 aa 的直线 ⇒\Rightarrow d(a)d(a) 是下包络 ⇒\Rightarrow 凹且分段线性。把"求积分"转化为"找折点",问题就成了可判定、可细分的形状。
  • 凹函数的中点判定是一个便宜好用的武器:只需一次函数求值, 就能确认"这段是直线",从而用梯形面积精确积分,误差只来自浮点而非离散化。
  • 容差要写成"绝对 ++ 相对"两项:绝对项扛小量级噪声,相对项随距离量级放大, 才能在答案高达 2×1092 \times 10^9 的数据上既不误判又不过度细分。
  • 输出格式属于答案的一部分:题面只写"一行一个实数",样例却是 2.5 / 13.0 这种去尾零的写法,因此按去尾零输出(至少留一位小数)是对齐判题数据最稳的选择。
  • 来源说明:本题素材源目录里带自造数据的生成脚本(data.py), 说明随仓 data/ 是按题面重建的、并非官方数据;题面本身也是网络重建版本, 与一本通官方原题可能处于描述口径上的偏差。随仓 std.cpp 的算法思路与本文一致, 已用真实数据逐点核对通过,故作为参考保留,未逐行照抄。