益智游戏

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

四次 Dijkstra 求出两组最短路的四个距离数组,筛出同时落在两条最短路上的点与边,答案即公共最短路 DAG 上的最长节点链。

OJ: roj

题目 ID: 1718

难度:提高

标签:图论最短路Dijkstra拓扑DPpython

创建: 2026-10-07 18:04

更新: 2026-10-07 18:04

形式化题目

给定 nn 个点、mm 条边的正权有向图(1≤li≤5×1081 \le l_i \le 5\times 10^8),以及四个点 A,B,C,DA,B,C,D。 小 P 要从 AA 沿最短路走到 BB,小 R 要从 CC 沿最短路走到 DD。 每回合一个角色可以走一条出边,也可以原地休息一回合(可以连续休息任意多回合)。 若某一时刻两个角色处在同一个点上,就得到一次奖励,但每个点最多只能得到一次。 求最多能得到多少次奖励;若 AA 到不了 BB 或 CC 到不了 DD,输出 −1-1。

把"回合"翻译成"时刻"。 由于可以无限次休息,两个角色到达各自途经点的时刻可以任意往后推, 唯一不能改变的是先后顺序:小 P 沿某条最短路依次经过 u1,u2,…u_1, u_2, \dots,小 R 沿某条最短路 依次经过 v1,v2,…v_1, v_2, \dots,只有"uu 在两个角色各自的路径上都先于 vv"时,才能把两人的到站时刻 对齐成"先在 uu 相遇、再在 vv 相遇"。于是

  • 能拿到奖励的点集 SS 必须同时是某条 A→BA \to B 最短路与某条 C→DC \to D 最短路的途经点集, 并且存在一个共同的先后顺序(在两条路径上都按同一顺序出现);
  • 因为"最多能获得多少次"是上界问题,等价于最大化 ∣S∣|S|。

四个距离数组。 记

dA[v]=dist⁡(A,v),dB[v]=dist⁡(v,B),dC[v]=dist⁡(C,v),dD[v]=dist⁡(v,D), d_A[v] = \operatorname{dist}(A,v),\quad d_B[v] = \operatorname{dist}(v,B),\quad d_C[v] = \operatorname{dist}(C,v),\quad d_D[v] = \operatorname{dist}(v,D),

并记 DAB=dA[B]D_{AB} = d_A[B]、DCD=dC[D]D_{CD} = d_C[D](两人各自的最短路长度)。 dA,dCd_A, d_C 在原图上从起点跑单源最短路即可;dB,dDd_B, d_D 是"到某点的距离", 在原图的反图上从 BB、DD 跑单源最短路即可。

一个点能不能被两人共同访问? 点 vv 落在某条 A→BA \to B 最短路上,当且仅当

dA[v]+dB[v]=DAB, d_A[v] + d_B[v] = D_{AB},

(必要性:该最短路被 vv 切成两段,长度就是 dA[v]d_A[v] 与 dB[v]d_B[v];充分性:把两段拼起来即一条最短路。) 同理 vv 落在某条 C→DC \to D 最短路上当且仅当 dC[v]+dD[v]=DCDd_C[v] + d_D[v] = D_{CD}。记

U={ v∣dA[v]+dB[v]=DAB ∧ dC[v]+dD[v]=DCD }, U = \{\, v \mid d_A[v] + d_B[v] = D_{AB} \ \wedge\ d_C[v] + d_D[v] = D_{CD} \,\},

UU 就是"有资格被共同访问"的点集,答案的取值必在 UU 内。

两点能不能按同一先后顺序先后被访问? 若 uu 在 UU 里、边 (u,v,w)(u,v,w) 同时满足

dA[u]+w+dB[v]=DAB∧dC[u]+w+dD[v]=DCD, d_A[u] + w + d_B[v] = D_{AB} \quad \wedge \quad d_C[u] + w + d_D[v] = D_{CD},

则这条边同时落在某条 A→BA \to B 最短路与某条 C→DC \to D 最短路上(下称公共最短路边), 把它接进 SS 一定不破坏可行性。反过来,一条由公共最短路边拼成的 u→vu \to v 路径长度 同时等于 dA[v]−dA[u]d_A[v] - d_A[u] 与 dC[v]−dC[u]d_C[v] - d_C[u],两人都能沿它走。

为什么用"公共边"就够了(等价性)。 设 u,v∈Uu, v \in U,且既有一条 A→BA \to B 最短路经过 uu 再经过 vv、 也有一条 C→DC \to D 最短路经过 uu 再经过 vv。把这两条最短路在 u,vu, v 之间的截段分别记为 Q1,Q2Q_1, Q_2, 则两者的长度都等于 dist⁡(u,v)=ℓ\operatorname{dist}(u,v) = \ell,因为 Q1Q_1 的长度是 dA[v]−dA[u]d_A[v] - d_A[u]、 Q2Q_2 的长度是 dC[v]−dC[u]d_C[v] - d_C[u],而它们又都是 u→vu \to v 的最短路径。 取 Q1=x0(=u),x1,…,xk(=v)Q_1 = x_0(=u), x_1, \dots, x_k(=v),沿它 dCd_C 每段至多增加该段边权,于是

dC[v]−dC[u]=ℓ=∑iwi  ≥  ∑i(dC[xi+1]−dC[xi])=dC[v]−dC[u], d_C[v] - d_C[u] = \ell = \sum_i w_i \;\ge\; \sum_i \bigl(d_C[x_{i+1}] - d_C[x_i]\bigr) = d_C[v] - d_C[u],

两头相等,所以每一段都恰好增加 wiw_i:dC[xi+1]=dC[xi]+wid_C[x_{i+1}] = d_C[x_i] + w_i。 再对 xjx_j 用三角不等式 $d_D[x_j] \le (\text{沿 } Q_1 \text{ 从 } x_j \text{ 到 } v \text{ 的长度}) + d_D[v] = \bigl(\ell - (d_C[x_j] - d_C[u])\bigr) + d_D[v],代入 $d_D[v] = D_{CD} - d_C[v] 与 ℓ=dC[v]−dC[u]\ell = d_C[v] - d_C[u] 得 dC[xj]+dD[xj]≤DCDd_C[x_j] + d_D[x_j] \le D_{CD},而 ≥\ge 方向恒成立,故 xj∈Ux_j \in U 且 Q1Q_1 的每条边都是公共最短路边。

也就是说:"公共最短路边拼成的路径"与"两人各自都存在的最短截段"是等价的, 按公共边做最长链 DP 不会漏解。这一点也是后面 dpdp 能只在 UU 上取初值的原因。

于是答案就是:把 UU 当作点集、把公共最短路边当作有向边,得到一张 DAG,求它的最长节点链 (即链上点的个数);U=∅U = \varnothing 时答案为 00。

正解

思路

第一步:四次 Dijkstra。 原图跑两次(起点 AA、CC),反图跑两次(起点 BB、DD), 得到 dA,dC,dB,dDd_A, d_C, d_B, d_D 四个数组。若 dA[B]d_A[B] 或 dC[D]d_C[D] 仍为无穷大,说明有人走不到终点, 直接输出 −1-1。用二叉堆实现,复杂度 O((n+m)log⁡n)O((n+m)\log n);n≤5×104n \le 5\times10^4、m≤2×105m \le 2\times10^5 绰绰有余。

第二步:筛出 UU。 一次线性扫描,dA[v]+dB[v]=DABd_A[v] + d_B[v] = D_{AB} 且 dC[v]+dD[v]=DCDd_C[v] + d_D[v] = D_{CD} 的 vv 进 UU,并把它的 DP 初值设成 11(这个点本身贡献一次奖励)。其余点初值 00。

以题面样例(n=5n=5,边 1→2(1)1\to2(1)、2→3(2)2\to3(2)、3→4(4)3\to4(4)、5→2(3)5\to2(3)、5→3(5)5\to3(5), A=1,B=3,C=5,D=4A=1,B=3,C=5,D=4)为例,四个数组与判定结果是:

vv dA[v]d_A[v] dB[v]d_B[v] dA+dBd_A+d_B dC[v]d_C[v] dD[v]d_D[v] dC+dDd_C+d_D 在 UU 中
1 0 3 3 = DABD_{AB} ∞ 7 ∞ 否
2 1 2 3 = DABD_{AB} 3 6 9 = DCDD_{CD} 是
3 3 0 3 = DABD_{AB} 5 4 9 = DCDD_{CD} 是
4 7 0 7 9 0 9 = DCDD_{CD} 否
5 ∞ 9 ∞ 0 9 9 = DCDD_{CD} 否

其中 DAB=3D_{AB} = 3、DCD=9D_{CD} = 9。点 11 虽然在小 P 的最短路上,但小 R 从 55 出发根本走不到它; 点 44 反过来只在小 R 的路上。只有 {2,3}\{2,3\} 同时在两条最短路上。

第三步:在公共最短路 DAG 上做最长链 DP。 先看边 (2,3,2)(2,3,2): dA[2]+2+dB[3]=1+2+0=3=DABd_A[2] + 2 + d_B[3] = 1 + 2 + 0 = 3 = D_{AB}, dC[2]+2+dD[3]=3+2+4=9=DCDd_C[2] + 2 + d_D[3] = 3 + 2 + 4 = 9 = D_{CD},所以它是公共最短路边,链 2→32 \to 3 成立,答案 22。 样例输出 22,与题面一致:小 P 在 22 号点休息到小 R 走到 22,再一起走到 33,正好两次。

第四步:为什么按 dAd_A 排序就是拓扑序? 公共最短路边满足 dA[v]=dA[u]+w>dA[u]d_A[v] = d_A[u] + w > d_A[u](边权为正,w≥1w \ge 1),所以沿着公共边 dAd_A 严格递增。 把 UU 按 dAd_A 升序排一遍,遍历到 uu 时它的所有前驱都已经算完,一次线性 DP 即可:

dp[v]=max⁡(1, max⁡(u,v,w) 是公共边dp[u]+1),答案=max⁡v∈Udp[v] (空集时为 0). dp[v] = \max\bigl(1,\ \max_{(u,v,w)\ \text{是公共边}} dp[u] + 1\bigr), \qquad \text{答案} = \max_{v \in U} dp[v] \ (\text{空集时为 } 0).

不必显式建新图,也不必修掉原图里那些"只属于某一个人"的边——直接在原图的出边表上按上述 两个等式过滤即可,每个点的出边只扫一次。

边界。 三处容易错:

  1. AA 到不了 BB 或 CC 到不了 DD 输出 −1-1,注意这与"没有公共点、答案 00"是两回事;
  2. A=BA = B(小 P 原地不动)时 DAB=0D_{AB} = 0,UU 只可能含 AA 本身,答案 11;
  3. 最短路长度可达 49999×5×108≈2.5×101349999 \times 5\times10^8 \approx 2.5\times10^{13},所有距离与加法判定 必须用 64 位(Python 天然无此问题),比较"是否等于 DABD_{AB}"时也不能用"小于等于"之类的近似写法。

代码

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:04
# update_at: 2026-10-07 18:04

import sys
from heapq import heappop, heappush

INF = 4 * 10**18  # 不可达哨兵:远大于任何真实最短路长度(上界约 2.5*10^13)

type Graph = list[list[tuple[int, int]]]        # 邻接表:g[u] 里是 (邻居, 边权)
type Dists = tuple[list[int], list[int], list[int], list[int]]  # 四条最短路 dA/dB/dC/dD


def dijkstra(src: int, g: Graph, n: int) -> list[int]:
    """src 到各点的最短路长度,不可达为 INF;g 传反图时求的就是"到 src 的最短路"。"""
    dist = [INF] * (n + 1)
    dist[src] = 0
    pq = [(0, src)]
    while pq:
        du, u = heappop(pq)
        if du > dist[u]:
            continue                       # 过期堆元素
        for v, w in g[u]:
            nd = du + w
            if nd < dist[v]:
                dist[v] = nd
                heappush(pq, (nd, v))
    return dist


def max_rewards(g: Graph, dists: Dists, targets: tuple[int, int]) -> int:
    """最大奖励数:公共最短路 DAG 上的最长节点链;有一人到不了终点时返回 -1。

    边 (u,v,w) 能接链当且仅当它同时落在 A→B 与 C→D 的某条最短路上;
    沿这样的边 dA 严格增大,按 dA 排序遍历即拓扑序,一次线性 DP 收尾。
    """
    dA, dB, dC, dD = dists
    dab, dcd = targets                      # 两条最短路各自的长度
    if dab >= INF or dcd >= INF:            # 小 P 走不到 B 或小 R 走不到 D
        return -1

    shared = [v for v in range(1, len(dA)) if dA[v] + dB[v] == dab and dC[v] + dD[v] == dcd]
    dp = dict.fromkeys(shared, 1)           # 每个公共点本身就能换一次奖励
    for u in sorted(shared, key=dA.__getitem__):
        for v, w in g[u]:
            if dA[u] + w + dB[v] == dab and dC[u] + w + dD[v] == dcd:
                dp[v] = max(dp[v], dp[u] + 1)  # 边成立则 v 必是公共点(见 index.md 证明)
    return max(dp.values(), default=0)      # 没有公共点时答案就是 0


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)

    g: Graph = [[] for _ in range(n + 1)]
    rg: Graph = [[] for _ in range(n + 1)]
    for _ in range(m):
        x, y, w = next(data), next(data), next(data)
        g[x].append((y, w))
        rg[y].append((x, w))
    A, B, C, D = next(data), next(data), next(data), next(data)

    # dB、dD 是"到 B / 到 D 的距离",在反图上跑即可
    dA, dB, dC, dD = (dijkstra(A, g, n), dijkstra(B, rg, n),
                      dijkstra(C, g, n), dijkstra(D, rg, n))
    print(max_rewards(g, (dA, dB, dC, dD), (dA[B], dC[D])))


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:04
 * update_at: 2026-10-07 18:04
 */
// main.cpp:益智游戏(一本通 1718)。
// 4 次 Dijkstra 求出 dA(A→v)、dB(v→B)、dC(C→v)、dD(v→D),
// 筛出「同时在 A→B 与 C→D 最短路上的点」以及「同时在两条最短路上的边」,
// 答案就是这张公共最短路 DAG 上的最长节点链(沿边 dA 严格递增,按 dA 排序即可线性 DP)。
// 与 main.py 同一算法;权值可达 5e8、最短路长度可达 1e14,故所有距离一律 64 位。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, int> pli;

const int MAXN = 50005;   // 点数上界
const int MAXM = 200005;  // 边数上界
const ll INF = (ll)4e18;  // 不可达的哨兵(4e18 远大于任何真实最短路长度)

int n, m;                 // 点数、边数
int ex[MAXM], ey[MAXM], ew[MAXM]; // 第 i 条边:ex[i] -> ey[i],权 ew[i]

// 前向 / 反向 CSR 邻接表:start[v] .. start[v+1]-1 是 v 的出边在 to/wt 里的下标
int startF[MAXN + 2], startR[MAXN + 2];
int toF[MAXM], wtF[MAXM], toR[MAXM], wtR[MAXM];

ll dA[MAXN], dB[MAXN], dC[MAXN], dD[MAXN]; // 四组最短路
int dp[MAXN];                              // 公共最短路 DAG 上的最长链(节点数)

// 把边表压成 CSR:forward 为真建原图,为假建反图
// 建好后 v 的出边就是下标区间 [start[v], start[v+1])
void build(int *start, int *to, int *wt, bool forward) {
    static int cnt[MAXN + 2], cur[MAXN + 2];
    for (int v = 0; v <= n + 1; v++) cnt[v] = 0;
    for (int i = 0; i < m; i++) cnt[forward ? ex[i] : ey[i]]++; // 先数每个点的出度
    start[0] = start[1] = 0;
    for (int v = 1; v <= n; v++) start[v + 1] = start[v] + cnt[v]; // 前缀和定出各点区间的左端
    for (int v = 0; v <= n + 1; v++) cur[v] = start[v];
    for (int i = 0; i < m; i++) {
        int u = forward ? ex[i] : ey[i], v = forward ? ey[i] : ex[i];
        to[cur[u]] = v;
        wt[cur[u]] = ew[i];
        cur[u]++;
    }
}

// 从 src 出发的单源最短路,图由 CSR (start,to,wt) 给出
void dijkstra(int src, const int *start, const int *to, const int *wt, ll *dist) {
    for (int v = 1; v <= n; v++) dist[v] = INF;
    priority_queue<pli, vector<pli>, greater<pli> > pq;
    dist[src] = 0;
    pq.push(pli(0, src));
    while (!pq.empty()) {
        pli cur = pq.top();
        pq.pop();
        ll du = cur.first;
        int u = cur.second;
        if (du > dist[u]) continue; // 过期堆元素
        for (int e = start[u]; e < start[u + 1]; e++) {
            int v = to[e];
            ll nd = du + wt[e];
            if (nd < dist[v]) {
                dist[v] = nd;
                pq.push(pli(nd, v));
            }
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) scanf("%d %d %d", &ex[i], &ey[i], &ew[i]);
    int A, B, C, D;
    scanf("%d %d %d %d", &A, &B, &C, &D);

    build(startF, toF, wtF, true);
    build(startR, toR, wtR, false);
    dijkstra(A, startF, toF, wtF, dA); // dA[v] = dist(A,v)
    dijkstra(B, startR, toR, wtR, dB); // 反图从 B => dB[v] = dist(v,B)
    dijkstra(C, startF, toF, wtF, dC); // dC[v] = dist(C,v)
    dijkstra(D, startR, toR, wtR, dD); // 反图从 D => dD[v] = dist(v,D)

    if (dA[B] >= INF / 2 || dC[D] >= INF / 2) { // 某个人走不到终点
        printf("-1\n");
        return 0;
    }
    const ll dab = dA[B], dcd = dC[D];

    // 公共点:同时在两条最短路上;按 dA 升序就是公共 DAG 的拓扑序
    vector<int> order;
    for (int v = 1; v <= n; v++) {
        if (dA[v] + dB[v] == dab && dC[v] + dD[v] == dcd) {
            dp[v] = 1; // 这个点本身可以贡献一次奖励
            order.push_back(v);
        } else {
            dp[v] = 0;
        }
    }
    sort(order.begin(), order.end(), [](int x, int y) { return dA[x] < dA[y]; });

    // 公共边 (u,v,w):同时落在 A→B 与 C→D 的某条最短路上,沿它 DP 即可接上链
    for (size_t i = 0; i < order.size(); i++) {
        int u = order[i];
        for (int e = startF[u]; e < startF[u + 1]; e++) {
            int v = toF[e];
            ll w = wtF[e];
            if (dA[u] + w + dB[v] == dab && dC[u] + w + dD[v] == dcd && dp[u] + 1 > dp[v]) {
                dp[v] = dp[u] + 1;
            }
        }
    }

    int ans = 0;
    for (int v = 1; v <= n; v++) ans = max(ans, dp[v]); // 没有公共点时为 0
    printf("%d\n", ans);
    return 0;
}

复杂度

  • 时间:四次 Dijkstra 共 O((n+m)log⁡n)O((n+m)\log n);筛 UU 是 O(n)O(n);DP 对 UU 排序 O(nlog⁡n)O(n\log n)、 扫所有出边 O(m)O(m)。总体 O((n+m)log⁡n)O((n+m)\log n),最坏 n=5×104n = 5\times10^4、m=2×105m = 2\times10^5。
  • 空间:四个距离数组与 CSR/邻接表,O(n+m)O(n+m)。
  • 实测:本地 10 组数据全部通过。最大的一组 n=50000n = 50000、m=200000m = 200000(含 5×1085\times10^8 权值的 64 位压力组)C++ 版实测 0.03 s / 峰值约 12 MB;等长最短路最多的那组(n=49999n = 49999、m=200000m = 200000) 实测 0.06 s。Python 版同样两组分别 0.29 s 与 0.49 s,均在 2 s 限时内。

总结

  • "可以休息"把时间约束变成了顺序约束:两人到达同一节点的时刻总能靠等待对齐, 所以问题从"路径逐时刻对齐"退化成"两条最短路能否按同一顺序穿过同一个点集"。
  • 四个距离数组是这类题的万能钥匙:判断"点/边是否在某条最短路上"只需一次加法等式, 正反图各跑两次 Dijkstra 就够,不需要枚举任何一条具体的最短路。
  • 答案 = 公共最短路 DAG 上的最长链:链的 DP 初值只在 UU 中取 11, UU 为空自然得到 00,这样"无解 −1-1"与"答案 00"两种边界不会互相污染。
  • 正权保证按 dAd_A 排序即拓扑序,省掉了显式拓扑排序与建新图。

关于本题数据与题面的说明。 素材目录里带有数据生成脚本(data.py),说明这 10 组 .in / .out 是自行生成的(生成方式:脊线 + 等长绕行通道造出大量等长最短路、链式图 + 大权重边填充、 以及 n,mn, m 顶格的 64 位压力组),题面本身也是按公开题解重建的, 因此它与出题人原始数据、原始意图之间可能存在偏差:本地 .out 与本文解法、题面样例三者一致, 但这只能证明"自洽",不能代替官方数据验收。 另外,本题"答案 $= $ 公共最短路 DAG 上的最长链"这一模型已被上面的等价性证明 (以及小规模随机图上的暴力枚举对拍:约 4700 组随机小图,最长公共子序列暴力解与本文解法完全一致) 验证,模型本身不是近似。