把每个点拆成最短路与严格次短路两个状态跑 Dijkstra,最短路退位时条数一起搬走,答案取最短路条数加次短路恰好多 1 的条数。
OJ: roj
题目 ID: 1716
难度:提高
标签:图论最短路Dijkstra计数python
创建: 2026-10-07 17:58
更新: 2026-10-07 17:58
形式化题目
给定有向图
注意
多组数据,每组一行整数;保证答案不超过
正解
思路
朴素做法。 枚举所有
该记什么。 题目要的不是一条路线,而是"长度恰好落在
: 的最短距离, 为达到它的路线条数; : 的严格次短距离( ), 为达到它的路线条数。
于是所求
为什么可以在"状态"上跑 Dijkstra。 把每个点
| 条件 | 动作 |
|---|---|
| 老的最短路退位成次短路( |
|
两个需要论证的点。
-
退位时条数可以整批搬走。 设老值为
、条数 , 而这些条数确实把 顶了下去。此后任何长度恰为 的 路线, 都不再满足 (那时 ), 而满足 ,会在第四类里被重新累加。 所以搬走 之后不会重复计数,也不会漏: 层的新贡献照旧进 。 -
状态出堆后不会被再次累加。 设
出堆后又被某个状态 贡献, 则要求 而 出堆更晚。 但 给出 , 距离更小的状态必然先出堆,矛盾。因此长度为 的路线,其前驱状态的 距离严格更小、一定先被确定, 在 出堆时已经收齐。 ——这也正是权值必须 的地方;若允许 权边或负权边, 同一状态会被后到的等长/更短路线二次贡献,本做法给出的计数就不可靠了。
有环会不会多算? 因为无自环且每条边
平行边。 邻接表里平行边各占一项,松弛时各自独立触发一次"
实现细节。
- 每个状态只被"确定"一次,出堆时若
d != dist[u][k]就丢弃(陈旧状态)。 - 也可以额外开一个
done[u][k]布尔数组显式去重,效果相同(本题main.cpp就是这么写的)。 组数据共用数组,每组开头必须把边表、 dist、cnt、done全部重置。、 、 可达 ,用链式前向星而非 vector邻接表 可以少一次清空。
样例逐组核算。 把程序内部的两个状态打出来看:
| 组 | 答案 | 说明 | |||
|---|---|---|---|---|---|
| 1 | 两条最短路 |
||||
| 2 | 两条 |
两组输出与题面样例逐字符一致(实际输出 3 / 2)。
代码
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 11:05
# update_at: 2026-10-07 11:05
import sys
from heapq import heappop, heappush
INF = 1 << 60 # 距离哨兵:任何真实路径长度都远小于它
# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type Graph = list[list[tuple[int, int]]] # 邻接表 g[u] = [(v, w), ...],重边各占一项
def count_routes(g: Graph, s: int, t: int) -> int:
"""返回 s->t 的「最短路条数 + 次短路恰好多 1 时的次短路条数」。
每个点拆成两个状态 (u, k):k=0 最短路、k=1 严格次短路,在状态上跑 Dijkstra。
边权 >= 1,所以长度为 dist[v][k] 的路线其前驱状态距离严格更小、必先出堆,
于是 (v,k) 出堆时它的条数已经收齐,出堆后用不着再回头累加。
"""
n = len(g) - 1 # g 用 1..n 编号,0 号位空占
dist = [[INF, INF] for _ in range(n + 1)]
cnt = [[0, 0] for _ in range(n + 1)] # 与 dist 逐格对应的路线条数
dist[s][0], cnt[s][0] = 0, 1
heap = [(0, s, 0)]
while heap:
d, u, k = heappop(heap)
if d != dist[u][k]:
continue # 陈旧状态:同一状态已被更短的距离取代
for v, w in g[u]:
nd = d + w
if nd < dist[v][0]:
if dist[v][0] < dist[v][1]:
# 老的最短路退位成次短路,条数一起搬走;此后同长度的贡献
# 都会落进下面 nd == dist[v][1] 那一支继续累加
dist[v][1], cnt[v][1] = dist[v][0], cnt[v][0]
heappush(heap, (dist[v][1], v, 1))
dist[v][0], cnt[v][0] = nd, cnt[u][k]
heappush(heap, (nd, v, 0))
elif nd == dist[v][0]:
cnt[v][0] += cnt[u][k] # 另一条等长路线
elif nd < dist[v][1]:
dist[v][1], cnt[v][1] = nd, cnt[u][k]
heappush(heap, (nd, v, 1))
elif nd == dist[v][1]:
cnt[v][1] += cnt[u][k]
if dist[t][1] == dist[t][0] + 1:
return cnt[t][0] + cnt[t][1]
return cnt[t][0]
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
out: list[str] = []
T = next(data)
for _ in range(T):
n, m = next(data), next(data)
g: Graph = [[] for _ in range(n + 1)]
for _ in range(m):
x, y, w = next(data), next(data), next(data)
g[x].append((y, w)) # 平行边各占一项,天然按「边集不同」区分路线
s, t = next(data), next(data)
out.append(str(count_routes(g, s, t)))
print('\n'.join(out))
if __name__ == "__main__":
solve()C++ 版(同一算法):
// 1716 次短路计数
// ---------------------------------------------------------------------------
// 题意:给定有向带权图与源点 s、汇点 t,求「长度 = 最短路长度」的 s->t 路线条数,
// 再加上「长度 = 最短路长度 + 1」的 s->t 路线条数(不存在则不加)。
// 两条路线不同 <=> 存在至少一条边属于其中一条而不属于另一条(边集不同),
// 因此重边各自独立计一次。
//
// 做法:把每个点拆成两个状态 (u,k),k=0 表示「到 u 的最短路」,k=1 表示
// 「到 u 的严格次短路」。在 (u,k) 上跑 Dijkstra:
// - 堆按距离升序弹出,每个状态只被确定一次,确定性后再暴力松弛出边;
// - 设边 u->v 权 w,松弛值 nd = dist[u][k] + w,分四类处理:
// nd < dist[v][0] -> 原 dist[v][0] 退位成 dist[v][1](计数一并搬过去),
// nd 顶替成新的 dist[v][0],计数置为 cnt[u][k];
// nd == dist[v][0] -> cnt[v][0] += cnt[u][k](同长度路径累加);
// nd < dist[v][1] -> 更新 dist[v][1] 并置计数为 cnt[u][k];
// nd == dist[v][1] -> cnt[v][1] += cnt[u][k]。
// 退位时「计数一并搬走」是正确的:此后所有长度等于旧 dist[v][0] 的路径
// 都会落进 nd == dist[v][1] 这一支,被继续累加到 cnt[v][1] 上。
//
// 关于计数何时定型:边权 >= 1,所以长度等于 dist[v][k] 的路径,其前驱状态
// 的距离严格小于 dist[v][k],一定先于 (v,k) 被弹出;于是 (v,k) 出堆时
// cnt[v][k] 已收齐。同理,状态出堆后再被累加是不可能的(那将要求 w <= 0)。
//
// 答案 = cnt[t][0] + (dist[t][1] == dist[t][0] + 1 ? cnt[t][1] : 0)。
//
// 复杂度:O(T * (n + m) log n) 时间(每个点两个状态、每条边被松弛至多两次),
// 堆内元素 O(n),其余数组 O(n),空间 O(n + m)。
// 数据规模:2 <= n <= 1000,1 <= m <= 10000,1 <= w <= 1000,答案 <= 1e9。
// ---------------------------------------------------------------------------
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1005; // 点数上界
const int MAXM = 10005; // 边数上界
const int INF = 0x3f3f3f3f; // 无穷大(两条最短路相加不会溢出)
// 链式前向星存边:重边各自占一条边,天然满足「边集不同即路线不同」
int head[MAXN], nxt[MAXM], to[MAXM], wt[MAXM], ecnt;
int n, m, s, t;
int dist[MAXN][2]; // dist[u][0] 最短路;dist[u][1] 严格次短路
ll cnt[MAXN][2]; // 对应条数
bool done[MAXN][2]; // 该状态是否已被最终确定
// 堆中元素:状态 (u, k) 及其距离 d
struct State {
int d, u, k;
bool operator<(const State &o) const { return d > o.d; } // 小根堆
};
// 加一条有向边 x -> y,权 w
void addEdge(int x, int y, int w) {
++ecnt;
to[ecnt] = y;
wt[ecnt] = w;
nxt[ecnt] = head[x];
head[x] = ecnt;
}
// 初始化一组数据
void init() {
ecnt = 0;
for (int i = 1; i <= n; ++i) {
head[i] = 0;
dist[i][0] = dist[i][1] = INF;
cnt[i][0] = cnt[i][1] = 0;
done[i][0] = done[i][1] = false;
}
}
// 用状态 (u, k) 的确定值去松弛 v,nd 为候选距离
void relax(int v, int nd, int u, int k, priority_queue<State> &pq) {
if (nd < dist[v][0]) {
// 老的最短路被顶下去,成为次短路(计数一起搬走)
if (dist[v][0] < dist[v][1]) {
dist[v][1] = dist[v][0];
cnt[v][1] = cnt[v][0];
pq.push(State{dist[v][1], v, 1});
}
dist[v][0] = nd;
cnt[v][0] = cnt[u][k];
pq.push(State{nd, v, 0});
} else if (nd == dist[v][0]) {
cnt[v][0] += cnt[u][k];
} else if (nd < dist[v][1]) {
dist[v][1] = nd;
cnt[v][1] = cnt[u][k];
pq.push(State{nd, v, 1});
} else if (nd == dist[v][1]) {
cnt[v][1] += cnt[u][k];
}
}
// 单组数据的求解(调用前需已 init() 并读入全部边)
ll solve() {
priority_queue<State> pq;
dist[s][0] = 0;
cnt[s][0] = 1;
pq.push(State{0, s, 0});
while (!pq.empty()) {
State cur = pq.top();
pq.pop();
int u = cur.u, d = cur.d, k = cur.k;
if (done[u][k] || d != dist[u][k]) continue; // 已经确定过 / 陈旧状态
done[u][k] = true;
for (int e = head[u]; e; e = nxt[e]) {
int v = to[e];
relax(v, d + wt[e], u, k, pq);
}
}
ll ans = cnt[t][0];
// 只额外统计「恰好比最短路多 1 个单位」的那一层
if (dist[t][1] == dist[t][0] + 1) ans += cnt[t][1];
return ans;
}
int main() {
int T;
if (scanf("%d", &T) != 1) return 0;
while (T--) {
if (scanf("%d %d", &n, &m) != 2) break;
init(); // 先清空上一组数据的边表与距离,再向其中加边
for (int i = 0; i < m; ++i) {
int x, y, w;
scanf("%d %d %d", &x, &y, &w);
addEdge(x, y, w);
}
scanf("%d %d", &s, &t);
printf("%lld\n", solve());
}
return 0;
}复杂度
- 时间:每个点两个状态、每条边被松弛至多两次。堆中每个状态最多因距离被更新而入堆
若干次,但只被确定一次,故为
每组数据, 组总计 。 - 空间:
dist / cnt / done各,链式前向星 ,堆 , 合计 ;按 、 计约几百 KB, 远低于 64 MB 限制。 - 与 C++ 解法的关系:
main.py是同一算法的 Python 版本,用heapq与邻接表, 复杂度同阶。实测 10 个测试点全部在 0.05 s 内跑完,Python 侧无 TLE 风险。
总结
- 计数问题的第一反应是"把答案改造成可加的量":本题不是求一条最短路,而是求两个 长度层上的条数,于是最短路计数被原样推广到"最近的两层"。
- 点拆成状态是最短路计数的通用外壳:
的 只有 两档,但它让 “次短路"从"需要额外讨论的东西"变成"状态图上的一个普通点”,松弛逻辑仍是 Dijkstra 那一套。 - 退位要连计数一起搬走:
时若只搬距离不搬条数, 就会漏掉全部老最短路的贡献;搬走之后同长度的新贡献又会自动落进 ,所以既不重也不漏。 只在次短路恰好多 时才加:题面要的是"恰好多一个单位距离"的路线, 时 里的路线一律不计。 - 权值
是算法正确性的前提(保证等长路线的前驱状态先出堆)。 本题数据满足该条件;若换成 权边,需改用"距离分层 + 拓扑序"或 BFS 式惰性计数。 - 重边必须各占一条边:题面的"路线不同"按边集判定,平行边是不同路线,
样例 2 的答案
就建立在两条 权为 的平行边上。
附注:素材与数据来源
- 本题题面与 POJ 3463 Sightseeing 的输入输出样例逐字一致,可视为同一题的收录版本;
std.cpp的头部注释也记录了这一点,并说明其算法是"按公开题解思路自行重写"而非逐行复制。 - 本目录的
std.cpp已实际编译(g++-16 -O2)并在随仓的 10 个测试点、以及题面样例上 与期望输出逐点比对,结果全部一致,故其算法(状态拆点 + Dijkstra 计数)与题面自洽, 本文的main.cpp/main.py按同一算法独立重写。 - 素材源目录同时带有数据生成脚本
data.py,说明data/是自造的(10 组, 分层覆盖边界、小规模、顶格、大答案 与 等分支), 并非官方原始数据。因此"本地全部测试点通过"不等于官方 AC, 题面本身也可能与官方原题存在偏差(例如是否要求输出次短路条数之和而非合并为一个整数)。 本文按题面字面口径实现:每组只输出一个整数。