四次 Dijkstra 求出两组最短路的四个距离数组,筛出同时落在两条最短路上的点与边,答案即公共最短路 DAG 上的最长节点链。
OJ: roj
题目 ID: 1718
难度:提高
标签:图论最短路Dijkstra拓扑DPpython
创建: 2026-10-07 18:04
更新: 2026-10-07 18:04
形式化题目
给定
把"回合"翻译成"时刻"。 由于可以无限次休息,两个角色到达各自途经点的时刻可以任意往后推,
唯一不能改变的是先后顺序:小 P 沿某条最短路依次经过
- 能拿到奖励的点集
必须同时是某条 最短路与某条 最短路的途经点集, 并且存在一个共同的先后顺序(在两条路径上都按同一顺序出现); - 因为"最多能获得多少次"是上界问题,等价于最大化
。
四个距离数组。 记
并记
一个点能不能被两人共同访问? 点
(必要性:该最短路被
两点能不能按同一先后顺序先后被访问? 若
则这条边同时落在某条
为什么用"公共边"就够了(等价性)。 设
两头相等,所以每一段都恰好增加
也就是说:"公共最短路边拼成的路径"与"两人各自都存在的最短截段"是等价的,
按公共边做最长链 DP 不会漏解。这一点也是后面
于是答案就是:把
正解
思路
第一步:四次 Dijkstra。 原图跑两次(起点
第二步:筛出
以题面样例(
| 在 |
|||||||
|---|---|---|---|---|---|---|---|
| 1 | 0 | 3 | 3 = |
∞ | 7 | ∞ | 否 |
| 2 | 1 | 2 | 3 = |
3 | 6 | 9 = |
是 |
| 3 | 3 | 0 | 3 = |
5 | 4 | 9 = |
是 |
| 4 | 7 | 0 | 7 | 9 | 0 | 9 = |
否 |
| 5 | ∞ | 9 | ∞ | 0 | 9 | 9 = |
否 |
其中
第三步:在公共最短路 DAG 上做最长链 DP。 先看边
第四步:为什么按
不必显式建新图,也不必修掉原图里那些"只属于某一个人"的边——直接在原图的出边表上按上述 两个等式过滤即可,每个点的出边只扫一次。
边界。 三处容易错:
到不了 或 到不了 输出 ,注意这与"没有公共点、答案 "是两回事; (小 P 原地不动)时 , 只可能含 本身,答案 ; - 最短路长度可达
,所有距离与加法判定 必须用 64 位(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++ 版(同一算法):
/**
* 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 共
;筛 是 ;DP 对 排序 、 扫所有出边 。总体 ,最坏 、 。 - 空间:四个距离数组与 CSR/邻接表,
。 - 实测:本地 10 组数据全部通过。最大的一组
、 (含 权值的 64 位压力组)C++ 版实测 0.03 s / 峰值约 12 MB;等长最短路最多的那组( 、 ) 实测 0.06 s。Python 版同样两组分别 0.29 s 与 0.49 s,均在 2 s 限时内。
总结
- "可以休息"把时间约束变成了顺序约束:两人到达同一节点的时刻总能靠等待对齐, 所以问题从"路径逐时刻对齐"退化成"两条最短路能否按同一顺序穿过同一个点集"。
- 四个距离数组是这类题的万能钥匙:判断"点/边是否在某条最短路上"只需一次加法等式, 正反图各跑两次 Dijkstra 就够,不需要枚举任何一条具体的最短路。
- 答案 = 公共最短路 DAG 上的最长链:链的 DP 初值只在
中取 , 为空自然得到 ,这样"无解 "与"答案 "两种边界不会互相污染。 - 正权保证按
排序即拓扑序,省掉了显式拓扑排序与建新图。
关于本题数据与题面的说明。 素材目录里带有数据生成脚本(data.py),说明这 10 组 .in / .out
是自行生成的(生成方式:脊线 + 等长绕行通道造出大量等长最短路、链式图 + 大权重边填充、
以及 .out 与本文解法、题面样例三者一致,
但这只能证明"自洽",不能代替官方数据验收。
另外,本题"答案 $= $ 公共最短路 DAG 上的最长链"这一模型已被上面的等价性证明
(以及小规模随机图上的暴力枚举对拍:约 4700 组随机小图,最长公共子序列暴力解与本文解法完全一致)
验证,模型本身不是近似。