运输中转站计数
P5948. 运输中转站计数
场次:2026年10月28日-非AI方向 · 来源:CodeFun2000 P5948
题目描述
一家物流企业共有 座中转站,各站依次标记为 至 。站点间铺设了若干运输线路,每条线路都只支持指定方向的运输。
现已获得该网络的全部线路资料,需要回答一次运输路径计数问题。
请统计从中转站 启程、沿线路移动恰好 次后停在中转站 的路径总数。同一站点可以在途中反复到访,已经走过的线路也能够再次使用。只要经过的站点序列有一处不同,就视为两条不同路径。
输入格式
- 首行给出两个整数 、,依次代表站点总数和线路总数。
- 下一行给出三个整数 、、,依次代表出发站、目的站和必须使用的线路条数。
- 随后有 行,各行给出整数 、,说明存在一条由站点 驶向站点 的线路。
数据范围:
- ;
- ;
- ;
- ,;
- ,即线路不会连接站点自身;
- 任意一对有序站点之间至多存在一条线路。
输出格式
输出一个整数,表示符合要求的路径总数;若没有可行路径,则输出 。答案无需取模。
示例
示例 1
输入:
5 7
2 5 4
2 3
3 2
3 4
4 3
3 5
2 5
5 1输出:
2说明: 从站点 启程,使用 条线路后停在站点 ,有以下两种走法:
- ;
- 。
两种走法都再次到访了站点 。
示例 2
输入:
6 6
2 6 2
2 1
1 6
2 4
4 6
2 5
5 6输出:
3说明: 由站点 出发,使用 条线路到站点 ,可选择 、 或 。
示例 3
输入:
5 4
4 1 1
4 2
2 1
1 5
5 3输出:
0说明: 站点 没有直接驶向站点 的线路,因此只使用 条线路无法抵达目的站。
解题思路
要数的东西:长度恰好的有向走法
一条合规路径就是一个站点序列
其中每一对相邻站点 都必须是一条真实存在的线路。判定的两个条件是「长度为 」和「终点是 」,中间怎么绕都不受限制:站点可以重访,线路可以重复使用。
题面还多加了一句「任意一对有序站点之间至多存在一条线路」。这句话的作用是让「站点序列」与「线路序列」一一对应:两站之间没有第二条边可挑,所以只要站点序列不同,路径就一定不同,计数时不必再考虑同一对站点之间的多重边。建图时每条线路只存一次就够了。
数据范围给出的信号: 不行,但每一步只有 种状态
先看最直白的做法:从 出发做 DFS,每到一个站点就把它的所有出边都试一遍,走满 步时检查是否落在 。每个站点最多有 条出边,所以搜索树最多展开
条分支。、 都很小,这个数字却大得离谱 —— 因为搜索树里绝大多数分支在重复走同一条路。
真正决定「后面还能怎么走」的信息只有一件:现在站在哪个站点,已经走了几步。至于前面是怎么绕过来的,对后续的可选线路没有任何影响。于是可以把「所有可能的走法」折叠成 个格子,每个格子只记一个数:走到这一步、停在这个站点的路径有多少条。
这就是「状态压缩」在这里的全部含义 —— 不是技巧,而是发现大量路径在「当前站点」这一维度上完全等价。
状态与转移:一条边把计数搬过去
记 为「恰好走 步后停在中转站 」的路径条数。初始时一步都还没走,只有 是可达的:
每走一步,就是把 里的每一条路径延伸出 的一条出边:
这个式子读起来就是「所有能一步走到 的站点,把它们各自的路径数加起来」。写成代码时沿边推进比按站点枚举更省事:
dp = [0] * (n + 1)
dp[s] = 1 # 第 0 步:只有起点有 1 条空路径
for _ in range(steps): # 走 steps 步
nxt = [0] * (n + 1) # 下一步的计数,先清零
for u in range(1, n + 1):
cnt = dp[u]
if cnt: # 这个站点在当前步不可达就跳过
for v in graph[u]: # 枚举 u 的每一条出边
nxt[v] += cnt # 同一对站点只有一条边,直接加
dp = nxt
print(dp[t])graph[u] 里存的是 能直接驶向的站点,所以内层循环的次数等于当前步真正可达的那些站点的出边数之和,最坏是 。
为什么要用一个新数组 nxt
转移式左边的下标是 、右边是 ,两者必须分开存放。如果偷懒就地累加:
for u in range(1, n + 1):
if dp[u]:
for v in graph[u]:
dp[v] += dp[u] # 就地改,会把下一步的计数混进这一步那么本次循环里刚写进 dp[v] 的数,会在后面某个 的时刻被当成「当前步的计数」继续往下搬。走 步的循环实际上允许路径无限延长,答案会明显偏大:示例 2 会输出 而不是 ,示例 1 会输出 而不是 。
正确的做法是每轮新开一个数组、算完再整体换过去,这也是上面代码里 nxt 与 dp = nxt 的作用。
实现落点
dp[s] = 1:第 步的空路径。 与 允许相同,此时「绕一圈回到起点」也被正常计入;if cnt:只是省掉不可达站点的空转,删掉也不影响正确性;- 外层
for _ in range(steps)走满 次,中途不提前判断「到 了没有」—— 提前停在 就变成「至多 步」,那是对题意的误读; - 最后打印
dp[t],没有路径时它自然就是 。
完整代码实现
"""
P5948. 运输中转站计数 - 按步数滚动的图上路径计数
给定 N 座中转站与 M 条有向线路,统计从 S 出发、恰好走 L 条线路后
停在 T 的路径条数。站点与线路都可以重复经过,站点序列不同即不同路径。
输入格式:
- 首行两个整数 N、M;
- 次行三个整数 S、T、L;
- 随后 M 行,每行两个整数 u、v,表示一条 u -> v 的线路。
输出格式:
- 一个整数:符合条件的路径条数;无解输出 0。
核心思路:
dp[v] 表示"恰好走完当前步数后停在 v"的路径条数。走一步就是沿每条出边
把计数搬到邻居上,滚动 L 次。起点在第 0 步有 1 条空路径。
每一步都用新数组承接,绝不能就地累加(那会让同一步的结果被反复使用)。
时间复杂度:O(L * (N + M))
空间复杂度:O(N)
"""
# https://codefun2000.com/p/P5948
import sys
# @sample-start
"""
样例输入 1:
5 7
2 5 4
2 3
3 2
3 4
4 3
3 5
2 5
5 1
样例输出 1:
2
"""
# @sample-end
# @sample-start
"""
样例输入 2:
6 6
2 6 2
2 1
1 6
2 4
4 6
2 5
5 6
样例输出 2:
3
"""
# @sample-end
# @sample-start
"""
样例输入 3:
5 4
4 1 1
4 2
2 1
1 5
5 3
样例输出 3:
0
"""
# @sample-end
def solve():
data = sys.stdin.buffer.read().split()
if not data:
return
it = iter(data)
n = int(next(it))
m = int(next(it))
s = int(next(it))
t = int(next(it))
steps = int(next(it))
graph = [[] for _ in range(n + 1)]
for _ in range(m):
u = int(next(it))
v = int(next(it))
graph[u].append(v) # 有向边:只记 u -> v
dp = [0] * (n + 1)
dp[s] = 1 # 第 0 步:只有起点有 1 条空路径
for _ in range(steps):
nxt = [0] * (n + 1)
for u in range(1, n + 1):
cnt = dp[u]
if cnt: # 不可达的站点直接跳过
for v in graph[u]:
nxt[v] += cnt # 有序站点对之间至多一条边,无需乘重数
dp = nxt
print(dp[t])
def run_tests():
"""运行嵌入的示例,方便本地自测。"""
import io
cases = [
(
"5 7\n2 5 4\n2 3\n3 2\n3 4\n4 3\n3 5\n2 5\n5 1\n",
"2",
),
(
"6 6\n2 6 2\n2 1\n1 6\n2 4\n4 6\n2 5\n5 6\n",
"3",
),
(
"5 4\n4 1 1\n4 2\n2 1\n1 5\n5 3\n",
"0",
),
# 起点即终点:绕一条自环走不出去,但可以 1->2->1 走 2 步回来
("2 2\n1 1 2\n1 2\n2 1\n", "1"),
# 同样的图走 3 步:1->2->1->2 到不了 1
("2 2\n1 1 3\n1 2\n2 1\n", "0"),
]
for i, (inp, expected) in enumerate(cases, 1):
old_stdin, old_stdout = sys.stdin, sys.stdout
sys.stdin = io.TextIOWrapper(io.BytesIO(inp.encode("utf-8")))
sys.stdout = io.StringIO()
try:
solve()
output = sys.stdout.getvalue().strip()
finally:
sys.stdin, sys.stdout = old_stdin, old_stdout
status = "✓" if output == expected else "✗"
print(f"用例 {i}: 期望={expected!r}, 实际={output!r} {status}")
if __name__ == "__main__":
if len(sys.argv) > 1 and sys.argv[1] == "--test":
run_tests()
else:
solve()示例推演
示例 1:,从 出发走 步到
图里的边是 、、、、、、。
第 步只有起点有计数:
| 步数 | |||||
|---|---|---|---|---|---|
第 步: 的出边是 与 ,各搬过去 条 → 。
第 步: 的出边是 、、,各搬 ; 的出边是 ,搬 :
| 步数 | |||||
|---|---|---|---|---|---|
第 步: 搬给 、; 搬给 ; 搬给 ; 没有出边。于是 ,其余各 :
| 步数 | |||||
|---|---|---|---|---|---|
第 步: 分别搬给 、、,各 ; 搬给 :
| 步数 | |||||
|---|---|---|---|---|---|
答案 。这 条正是题面列出的两条:
- 第 步停在 的路径有两条( 与 ),它们各自沿 走到 ,就是 与 ;
- 第 步停在 的那 条是 ,它只剩一条出边 ,走不到 ,所以不计入答案。
这个对比正好说明了 DP 在做什么:两条不同前缀在第 步「停在同一站」之后就完全等价,只需记一个「」,不必记住它们各自长什么样。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| DFS 枚举所有走法 | 、 时约 条分支,必然超时 | ||
| 按步滚动的路径计数(最优) | 每轮遍历一遍站点与全部出边,、 |
时间里的 来自每轮扫一遍「哪些站点有计数」, 来自把所有出边各走一次;空间只有两个长度为 的数组,与 、 都无关。
易错点总结
1. 就地累加,没有另开数组
把 nxt = [0] * (n + 1) 删掉、直接把 nxt[v] += cnt 写成 dp[v] += cnt,程序照样跑完,但同一步里刚加进去的计数会被后续站点继续搬运,等效于允许路径在 步之内无限延长。按站点编号从小到大推进时,示例 1 输出 (正确 ),示例 2 输出 (正确 )—— 结果偏大,且样例 3 仍然是 ,很容易被误判成「只错了个别情况」。
2. 转移用赋值而不是累加
写成 nxt[v] = dp[u] 时,同一个 有多条入边就只留下最后一条的计数。示例 2 中站点 的入边来自 、、,三份计数被覆盖成一份,输出 而不是 ;示例 1 因为每条入边只承载 或 条路径,错得更隐蔽 —— 输出 。
3. 把「恰好 步」做成「至多 步」
在循环末尾补一句 ans += dp[t],最后打印 ans 而不是 dp[t],就把「第 步停在 」的所有 都算了进去。示例 1 中第 、、、 步的 分别是 ,累加得 ,官方答案是 —— 多出来的三条路径都是「提前到达、还没走满 步」的走法。