连续图上的顺序会面问题

题目概述

给定一张 $n$ 个点、$m$ 条边的无向连通图。第 $i$ 条边连接 $u_i,v_i$，长度为 $w_i$。

你初始位于 $1$ 号点，需要依次与 $k$ 个网友见面，第 $i$ 个网友初始位于 $p_i$。

所有人的移动速度均为 $1$，并且可以：

• 在边的内部相遇；
• 在边上折返；
• 在任意位置等待；
• 在任意实数时刻发生相遇。

要求最小化与所有网友按照给定顺序完成见面的时间 $T$。

题目要求输出 $2T$，并保证 $2T$ 一定为整数。

数据范围：

$$ 2\le n\le 10^5 $$

$$ n-1\le m\le 2\times10^5 $$

$$ 1\le k\le20 $$

一、消除“依次见面”的限制

乍看之下，由于必须按照 $1,2,\ldots,k$ 的顺序见面，似乎需要设计复杂的动态规划。

实际上，“依次见面”这个限制可以完全消除。

设某个合法方案在时间 $T$ 完成全部会面。

假设第 $i$ 个网友在时刻 $t_i$、位置 $y_i$ 与你相遇。

由于第 $i$ 个网友从 $p_i$ 出发，速度为 $1$，因此：

$$ d(p_i,y_i)\le t_i $$

其中 $d(a,b)$ 表示图上两点之间的最短距离。

在与第 $i$ 个网友见面以后，你还需要继续运动，并最终在时刻 $T$ 完成所有见面。

设最终你所处的位置为 $x$。

从 $y_i$ 到 $x$ 的实际运动长度不超过剩余时间，因此：

$$ d(y_i,x)\le T-t_i $$

由三角不等式：

$$ d(p_i,x) \le d(p_i,y_i)+d(y_i,x) \le t_i+(T-t_i) =T $$

因此对于所有网友均有：

$$ d(p_i,x)\le T $$

同时你自己从 $1$ 号点出发，所以：

$$ d(1,x)\le T $$

于是任何合法方案都必然满足：

$$ T\ge \max_{s\in\{1,p_1,p_2,\ldots,p_k\}}d(s,x) $$

反过来，如果存在某个位置 $x$，使得：

$$ d(s,x)\le T $$

对于所有

$$ s\in\{1,p_1,p_2,\ldots,p_k\} $$

均成立，那么可以让所有人从时刻 $0$ 开始直接前往 $x$。

提前到达的人在 $x$ 等待。

在时刻 $T$ 时，所有人都已经位于 $x$，于是你可以在同一时刻按照：

$$ 1,2,\ldots,k $$

的顺序依次完成全部见面。

由于见面本身不消耗时间，这完全合法。

因此原问题严格等价于：

$$ \boxed{ T= \min_x \max_{s\in\{1,p_1,\ldots,p_k\}} d(s,x) } $$

其中 $x$ 可以位于图的顶点，也可以位于任意一条边的内部。

这实际上就是一个连续图上的 1-center 问题。

二、源点数量很少

定义所有相关起点组成的集合：

$$ S=\{1,p_1,p_2,\ldots,p_k\} $$

由于：

$$ k\le20 $$

因此：

$$ |S|\le21 $$

如果若干网友位于同一个点，或者某个网友本身就在 $1$ 号点，则重复的源点没有任何影响，可以直接去重。

设去重后的源点数量为 $q$，则：

$$ q\le21 $$

对于每个源点 $s_j$，运行一次 Dijkstra，计算：

$$ d_j[v]=d(s_j,v) $$

于是只需要运行至多 $21$ 次 Dijkstra。

三、中心位于顶点时

首先考虑最优中心 $x$ 恰好位于某个顶点 $v$。

此时覆盖所有源点所需的时间为：

$$ R(v)=\max_{1\le j\le q}d_j[v] $$

因此枚举全部顶点即可：

$$ T_{\text{vertex}} = \min_v R(v) $$

也就是：

$$ T_{\text{vertex}} = \min_v \max_j d_j[v] $$

这一部分复杂度为：

$$ O(qn) $$

但真正需要注意的是，最优位置可能位于某条边的内部。

四、分析一条边内部的距离函数

考虑一条边：

$$ (u,v,w) $$

边长为 $w$。

设边上的一个位置 $x$ 到端点 $u$ 的距离为 $t$，则：

$$ 0\le t\le w $$

它到端点 $v$ 的距离为：

$$ w-t $$

对于源点 $s_j$，到达 $x$ 时最后一定是从 $u$ 或 $v$ 进入这条边，因此：

$$ d(s_j,x) = \min \left( d_j[u]+t,\, d_j[v]+w-t \right) $$

定义：

$$ A_j=d_j[u] $$

$$ C_j=d_j[v]+w $$

那么：

$$ f_j(t) = \min(A_j+t,C_j-t) $$

其中：

• $A_j+t$ 是从 $u$ 进入边的路径；
• $C_j-t$ 是从 $v$ 进入边的路径。

因此 $f_j(t)$ 是两条直线的较小值。

两条直线的交点满足：

$$ A_j+t=C_j-t $$

所以：

$$ 2t=C_j-A_j $$

即：

$$ t_j=\frac{C_j-A_j}{2} $$

五、为什么转折点一定在边内部

根据最短路的三角不等式：

$$ d_j[u]\le d_j[v]+w $$

所以：

$$ A_j\le C_j $$

即：

$$ C_j-A_j\ge0 $$

另一方面：

$$ d_j[v]\le d_j[u]+w $$

因此：

$$ d_j[v]+w\le d_j[u]+2w $$

也就是：

$$ C_j-A_j\le2w $$

于是：

$$ 0\le C_j-A_j\le2w $$

从而：

$$ 0\le t_j\le w $$

因此每个源点对应的距离函数都恰好在这条边内部发生一次转折。

六、避免浮点数

由于最终只要求输出 $2T$，可以将边上的坐标扩大两倍。

定义：

$$ z=2t $$

于是：

$$ 0\le z\le2w $$

对于源点 $s_j$，定义转折点：

$$ S_j=C_j-A_j $$

那么：

$$ S_j=2t_j $$

而 $A_j,C_j$ 都是整数，所以 $S_j$ 也是整数。

这意味着整个算法都可以只使用整数运算，无需使用 double。

七、按照转折点排序

将这一条边上的所有源点按照：

$$ S_j=C_j-A_j $$

从小到大排序。

假设排序后：

$$ S_1\le S_2\le\cdots\le S_q $$

考虑某个区间：

$$ S_i\le z\le S_{i+1} $$

也就是：

$$ \frac{S_i}{2}\le t\le\frac{S_{i+1}}2 $$

对于前 $i$ 个源点，已经越过各自的转折位置，因此：

$$ f_j(t)=C_j-t $$

对于剩余的源点，还没有越过转折位置，因此：

$$ f_j(t)=A_j+t $$

于是这一段内所有源点距离的最大值为：

$$ F(t)= \max \left( \max_{j\le i}(C_j-t), \max_{j>i}(A_j+t) \right) $$

定义前缀最大值：

$$ P_i=\max_{j\le i}C_j $$

以及后缀最大值：

$$ Q_{i+1}=\max_{j>i}A_j $$

则：

$$ F(t) = \max(P_i-t,Q_{i+1}+t) $$

这已经变成了两条直线的最大值。

八、求一个区间内的最优位置

由于：

$$ z=2t $$

所以：

$$ 2F = \max(2P_i-z,2Q_{i+1}+z) $$

第一项关于 $z$ 单调递减，第二项关于 $z$ 单调递增。

因此它们的最大值构成一个 V 形函数。

如果交点位于当前区间内部，那么交点一定是最优位置。

令：

$$ 2P_i-z = 2Q_{i+1}+z $$

则：

$$ 2z=2P_i-2Q_{i+1} $$

因此：

$$ z=P_i-Q_{i+1} $$

由于 $z$ 必须位于：

$$ [S_i,S_{i+1}] $$

所以实际最优位置为：

$$ \boxed{ z= \operatorname{clamp} (P_i-Q_{i+1},S_i,S_{i+1}) } $$

其中：

$$ \operatorname{clamp}(x,l,r) = \min(\max(x,l),r) $$

得到 $z$ 后，这个位置对应的答案就是：

$$ \boxed{ 2F= \max(2P_i-z,2Q_{i+1}+z) } $$

于是每个区间都可以 $O(1)$ 求出最优答案。

九、边的两端为什么不需要额外处理

最左侧区间：

$$ 0\le z\le S_1 $$

中，所有源点都处于自己的转折点左边，所以：

$$ f_j(t)=A_j+t $$

因此：

$$ F(t)=\max_j A_j+t $$

显然随着 $t$ 增大而增大。

所以最优位置一定是：

$$ t=0 $$

也就是顶点 $u$。

类似地，在最右侧：

$$ S_q\le z\le2w $$

所有函数都为：

$$ C_j-t $$

因此整体随 $t$ 增大而减小，最优位置为：

$$ t=w $$

也就是顶点 $v$。

而所有顶点已经在前面枚举过，因此对于每条边，只需要处理相邻两个转折点之间的：

$$ q-1 $$

个区间即可。

十、为什么 $2T$ 一定是整数

现在也可以直接解释题目中“容易证明 $2T$ 一定是整数”的原因。

每条边内部可能成为最优解的位置，要么位于某个转折点：

$$ z=S_j $$

要么位于两条关键直线的交点：

$$ z=P_i-Q_{i+1} $$

其中：

$$ S_j,\ P_i,\ Q_i $$

全部都是整数。

所以最优位置对应的：

$$ z=2t $$

一定可以取整数。

而答案：

$$ 2T = \max(2P_i-z,2Q_{i+1}+z) $$

同样必然是整数。

因此整个程序使用 long long 即可，不需要任何浮点运算。

十一、完整算法

算法流程如下。

1. 将 $1,p_1,p_2,\ldots,p_k$ 放入源点集合，并去重。
2. 对每个源点运行一次 Dijkstra。

3. 枚举所有顶点 $v$，计算：

   $$ 2\max_j d_j[v] $$

   更新答案。

4. 枚举每条边 $(u,v,w)$：

   • 对每个源点计算：

     $$ A_j=d_j[u] $$

     $$ C_j=d_j[v]+w $$

     $$ S_j=C_j-A_j $$

   • 按照 $S_j$ 排序。

   • 计算 $C_j$ 的前缀最大值。

   • 计算 $A_j$ 的后缀最大值。

   • 枚举每对相邻转折点。

   • 求：

     $$ z= \operatorname{clamp} (P_i-Q_{i+1},S_i,S_{i+1}) $$

   • 用：

     $$ 2F= \max(2P_i-z,2Q_{i+1}+z) $$

     更新全局答案。

5. 输出最小的 $2T$。

十二、正确性证明

引理 1

设一个合法方案在时间 $T$ 完成，最终位置为 $x$，则对于任意网友起点 $p_i$：

$$ d(p_i,x)\le T $$

证明

假设第 $i$ 个网友在时间 $t_i$、位置 $y_i$ 与你见面。

由于网友的速度为 $1$：

$$ d(p_i,y_i)\le t_i $$

而你从 $y_i$ 到最终位置 $x$ 的剩余时间为 $T-t_i$，所以：

$$ d(y_i,x)\le T-t_i $$

由三角不等式：

$$ d(p_i,x) \le d(p_i,y_i)+d(y_i,x) \le T $$

证毕。

引理 2

若存在位置 $x$，满足对所有源点 $s$：

$$ d(s,x)\le T $$

则可以在时间 $T$ 内按照要求顺序完成全部见面。

证明

让你和所有网友同时从初始位置出发前往 $x$。

因为：

$$ d(s,x)\le T $$

所以所有人都可以在不晚于时间 $T$ 到达 $x$。

提前到达的人原地等待。

到达时间 $T$ 时所有人都位于 $x$，于是可以按照编号顺序依次完成所有见面。

由于见面不耗费时间，因此总时间不超过 $T$。

证毕。

定理 1

原问题的最优答案为：

$$ T= \min_x \max_{s\in S}d(s,x) $$

证明

由引理 1，任何合法方案的完成时间 $T$ 都不小于：

$$ \min_x\max_{s\in S}d(s,x) $$

由引理 2，对于使右侧达到最小值的位置 $x$，所有人直接前往 $x$ 即可在该时间内完成全部会面。

上下界相同，因此结论成立。

证毕。

引理 3

对于边 $(u,v,w)$ 上距 $u$ 为 $t$ 的位置 $x$，源点 $s_j$ 到 $x$ 的距离为：

$$ d(s_j,x) = \min(d_j[u]+t,d_j[v]+w-t) $$

证明

任意从图的其他部分进入边内部位置 $x$ 的路径，都必须先到达端点 $u$ 或 $v$。

从 $u$ 进入需要额外走 $t$，从 $v$ 进入需要额外走 $w-t$。

取两种方案中较短者即可。

证毕。

引理 4

在两个相邻转折点之间，目标函数可以写成：

$$ F(t) = \max(P_i-t,Q_{i+1}+t) $$

证明

在区间：

$$ S_i\le2t\le S_{i+1} $$

内，前 $i$ 个源点已经经过转折点，因此使用：

$$ C_j-t $$

其最大值为：

$$ P_i-t $$

剩余源点仍使用：

$$ A_j+t $$

其最大值为：

$$ Q_{i+1}+t $$

两部分取最大值即得结论。

证毕。

引理 5

在区间 $[S_i,S_{i+1}]$ 内，最优的 $z=2t$ 为：

$$ z= \operatorname{clamp} (P_i-Q_{i+1},S_i,S_{i+1}) $$

证明

该区间内：

$$ 2F= \max(2P_i-z,2Q_{i+1}+z) $$

其中第一项单调递减，第二项单调递增。

两条直线的交点为：

$$ z=P_i-Q_{i+1} $$

若交点位于区间内部，最大值在交点处最小。

若交点位于区间左侧，则整个区间中第二条直线占主导，最优位置为左端点。

若交点位于区间右侧，则第一条直线占主导，最优位置为右端点。

因此答案正是将交点限制在当前区间中，即：

$$ z= \operatorname{clamp} (P_i-Q_{i+1},S_i,S_{i+1}) $$

证毕。

定理 2

算法能够求出原问题的最优答案。

证明

根据定理 1，只需枚举连续图中所有可能的位置 $x$。

连续图中的任意位置要么：

• 是一个顶点；
• 位于某条边的内部。

算法显式枚举了所有顶点。

对于每一条边，根据引理 3，将每个源点的距离写成两条直线的最小值。

排序所有转折点后，整条边被划分为若干区间。

由引理 4 和引理 5，每个区间中的最优位置都被算法准确计算。

边最左端和最右端的最优位置分别是两个端点，而端点已经在顶点枚举中考虑。

所以算法检查了所有可能产生全局最优值的位置。

因此最终得到的答案就是原问题的最优答案。

证毕。

十三、复杂度分析

设去重后的源点数量为 $q$，其中：

$$ q\le21 $$

每个源点运行一次 Dijkstra。

使用优先队列时，复杂度为：

$$ O((n+m)\log n) $$

因此全部最短路复杂度：

$$ O(q(n+m)\log n) $$

枚举所有顶点需要：

$$ O(qn) $$

对于每条边，需要对 $q$ 个转折点排序：

$$ O(q\log q) $$

随后计算前后缀以及枚举区间：

$$ O(q) $$

所以所有边的复杂度：

$$ O(mq\log q) $$

最终总时间复杂度：

$$ \boxed{ O(q(n+m)\log n+mq\log q) } $$

由于：

$$ q\le21 $$

可以近似看作：

$$ O((n+m)\log n) $$

乘上一个约 $20$ 的常数。

存储 $q$ 份最短路数组需要：

$$ O(qn) $$

图本身需要：

$$ O(n+m) $$

因此空间复杂度：

$$ \boxed{ O(qn+n+m) } $$

十四、参考代码

#include <algorithm>
#include <array>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

using ll = long long;

constexpr ll INF = (1LL << 62);

struct Edge {
    int to;
    int w;
};

struct RawEdge {
    int u, v;
    int w;
};

struct Item {
    ll s;   // 转折点 z = 2t
    ll a;   // d[source][u]
    ll c;   // d[source][v] + w
};

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

    int n, m;
    cin >> n >> m;

    vector<vector<Edge>> graph(n);
    vector<RawEdge> edges;
    edges.reserve(m);

    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        --u;
        --v;

        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
        edges.push_back({u, v, w});
    }

    int k;
    cin >> k;

    vector<int> sources;
    sources.reserve(k + 1);
    sources.push_back(0);

    for (int i = 0; i < k; ++i) {
        int p;
        cin >> p;
        --p;
        sources.push_back(p);
    }

    // 重复的源点没有影响，可以去重
    sort(sources.begin(), sources.end());
    sources.erase(unique(sources.begin(), sources.end()), sources.end());

    int q = sources.size();

    // dist[j][v] 表示第 j 个源点到顶点 v 的最短距离
    vector<vector<ll>> dist(q, vector<ll>(n));

    auto dijkstra = [&](int idx) {
        auto &d = dist[idx];
        fill(d.begin(), d.end(), INF);

        int s = sources[idx];
        d[s] = 0;

        priority_queue<
            pair<ll, int>,
            vector<pair<ll, int>>,
            greater<pair<ll, int>>
        > pq;

        pq.push({0, s});

        while (!pq.empty()) {
            auto [du, u] = pq.top();
            pq.pop();

            if (du != d[u])
                continue;

            for (auto [v, w] : graph[u]) {
                ll nd = du + w;

                if (nd < d[v]) {
                    d[v] = nd;
                    pq.push({nd, v});
                }
            }
        }
    };

    for (int i = 0; i < q; ++i)
        dijkstra(i);

    ll ans2 = INF;

    // 最优中心位于某个顶点
    for (int v = 0; v < n; ++v) {
        ll mx = 0;

        for (int j = 0; j < q; ++j)
            mx = max(mx, dist[j][v]);

        ans2 = min(ans2, 2 * mx);
    }

    // 每条边上最多只有 21 个源点
    array<Item, 21> item;
    array<ll, 21> prefixC;
    array<ll, 21> suffixA;

    // 枚举最优中心位于边内部的情况
    for (auto [u, v, w_int] : edges) {
        ll w = w_int;

        for (int j = 0; j < q; ++j) {
            ll A = dist[j][u];
            ll C = dist[j][v] + w;

            // S = 2t = C - A
            ll S = C - A;

            item[j] = {S, A, C};
        }

        sort(
            item.begin(),
            item.begin() + q,
            [](const Item &x, const Item &y) {
                return x.s < y.s;
            }
        );

        // C 的前缀最大值
        prefixC[0] = item[0].c;

        for (int i = 1; i < q; ++i)
            prefixC[i] = max(prefixC[i - 1], item[i].c);

        // A 的后缀最大值
        suffixA[q - 1] = item[q - 1].a;

        for (int i = q - 2; i >= 0; --i)
            suffixA[i] = max(suffixA[i + 1], item[i].a);

        // 枚举两个相邻转折点之间的区间
        for (int i = 0; i + 1 < q; ++i) {
            ll lo = item[i].s;
            ll hi = item[i + 1].s;

            ll P = prefixC[i];
            ll Q = suffixA[i + 1];

            // 两条直线的理论交点
            ll z = P - Q;

            // 限制到当前区间
            z = max(z, lo);
            z = min(z, hi);

            ll cur2 = max(
                2 * P - z,
                2 * Q + z
            );

            ans2 = min(ans2, cur2);
        }
    }

    cout << ans2 << '\n';

    return 0;
}

十五、样例解释

样例中相关起点为：

$$ 1,2,3 $$

图中有：

$$ d(1,2)=1 $$

$$ d(1,3)=2 $$

$$ d(2,3)=3 $$

三个点实际上位于一条长度为 $3$ 的最短路径上：

$$ 2\rightarrow1\rightarrow3 $$

取这条长度为 $3$ 的路径的中点作为最终集合位置，则：

$$ T=\frac32 $$

因此：

$$ 2T=3 $$

所以输出：

3

总结

这道题最关键的两个观察是：

第一，所谓“按照顺序见网友”实际上不需要进行顺序 DP。

所有人完全可以直接向最终中心位置移动，因此问题等价于：

$$ \min_x\max_{s\in S}d(s,x) $$

第二，最优中心可能位于边内部。

对于一条边，每个源点对应的距离函数都是：

$$ \min(A_j+t,C_j-t) $$

将所有转折点排序后，相邻转折点之间的目标函数可以化成：

$$ \max(P-t,Q+t) $$

从而只需要求两条直线的交点。

最终利用 $k\le20$ 的条件，对至多 $21$ 个源点运行 Dijkstra，再对每条边处理至多 $21$ 个转折点，即可在数据范围内解决问题。