定长路径计数
给一个
n
n
n 阶有向图，每条边的边权均为
1
1
1，然后给一个整数
k
k
k，你的任务是对于所有点对
(
u
,
v
)
(u,v)
(u,v) 求出从
u
u
u 到
v
v
v 长度为
k
k
k 的路径的数量
乘法原理
P4159 [SCOI2009] 迷路 拆点建边
P2151 [SDOI2009] HH去散步重新定义dp方程然后转移，初始化从
t
=
1
t=1
t=1开始，方便后续转移
定长最短路P2886 [USACO07NOV] Cow Relays G
给你一个
n
n
n 阶加权有向图和一个整数
k
k
k。对于每个点对
(
u
,
v
)
(u,v)
(u,v) 找到从
u
u
u 到
v
v
v 的恰好包含
k
k
k 条边的最短路的长度
每次两个矩阵转移时只取最短
限长路径计数/最短路
给一个
n
n
n 阶有向图，边权为 1，然后给一个整数
k
k
k，你的任务是对于每个点对
(
u
,
v
)
(u,v)
(u,v) 找到从
u
u
u 到
v
v
v 长度小于等于
k
k
k 的路径的数量
给每个点加一个自环