4159

[传送门](https://www.luogu.com.cn/problem/P4159) 先思考$C_{i,j}$要么只有0和1两种值的情况，那么这种情况就是求矩阵$C^k$中的$C_{1,n}$的值。 证明：令矩阵$G=C^2=\sum\limits_{k=1}^nC(i,k)*C(k,j)$， ......

# 题目大意 给定一个带权无向图与距离 $t$，问有多少条从 $1$ 到 $n$ 路径长度为 $T$。 # 思路 ### 从特殊情况出发 先考虑权值只有 $0,1$ 的情况，我们设 $f_t[i][j]=k$ 代表从 $i$ 到 $j$ 经过的路径权值综合为 $t$ 的方案数共 $k$ 种。 那么我 ......

# [SCOI2009] 迷路 ## 题目背景 windy 在有向图中迷路了。 ## 题目描述 该有向图有 $n$ 个节点，节点从 $1$ 至 $n$ 编号，windy 从节点 $1$ 出发，他必须恰好在 $t$ 时刻到达节点 $n$。 现在给出该有向图，你能告诉 windy 总共有多少种不同的路径 ......

[TOC] ### [题目链接](https://www.luogu.com.cn/problem/P4159 "题目链接") ### 题目内容 [SCOI2009] 迷路 题目背景 windy 在有向图中迷路了。 题目描述 该有向图有 $n$ 个节点，节点从 $1$ 至 $n$ 编号，windy ......