2517. K边路径数

【题目描述】

已知有向图 $G$，请编程计算从点 $i$ 到点 $j$ 经过 $k$ 条边的路径数。

【输入格式】

第一行三个正整数 $N$、$M$ 和 $K$，分别表示有向图顶点数、边数和题意中的 $K$ 值。

接下来 $M$ 行，每行 $2$ 个正整数 $x$ 和 $y$，表示 $x$ 到 $y$ 有一条有向边。

【输出格式】

输出 $N$ 行 $N$ 列矩阵；

第 $i$ 行，第 $j$ 列的整数表示点 $i$ 到点 $j$ 经过 $k$ 条边的路径数；

【样例输入1】

5 8 2
1 2
1 3
1 4
2 3
2 5
3 4
3 5
4 5

【样例输出1】

0 0 1 1 3
0 0 0 1 1
0 0 0 0 1
0 0 0 0 0
0 0 0 0 0

【样例1说明】

如图所示，边数为 $2$ 的路径数：

$1 \longrightarrow 3：1 \rightarrow 2 \rightarrow 3：1$ 条

$1 \longrightarrow 4：1 \rightarrow 3 \rightarrow 4；1$ 条

$1 \longrightarrow 5：1 \rightarrow 2 \rightarrow 5，1 \rightarrow 3 \rightarrow 5，1 \rightarrow 4 \rightarrow 5；3$ 条

$2 \longrightarrow 4：2 \rightarrow 3 \rightarrow 4；1$ 条

$2 \longrightarrow 5：2 \rightarrow 3 \rightarrow 5；1$ 条

$3 \longrightarrow 5：3 \rightarrow 4 \rightarrow 5；1$ 条

【样例输入2】

5 8 3
1 2
1 3
1 4
2 3
2 5
3 4
3 5
4 5

【样例输出2】

0 0 0 1 2
0 0 0 0 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

【样例2说明】

如图所示，边数为 $3$ 的路径数：

$1 \longrightarrow 4：1 \rightarrow 2 \rightarrow 3 \rightarrow 4；1$ 条

$1 \longrightarrow 5：1 \rightarrow 2 \rightarrow 3 \rightarrow 5，1 \rightarrow 3 \rightarrow 4 \rightarrow 5；2$ 条

$2 \longrightarrow 5：2 \rightarrow 3 \rightarrow 4 \rightarrow 5；1$ 条

【数据规模】

$100\%$ 的数据,$1 \leq n \leq 150,1 \leq k \leq 15$.

【来源】

$Mr$ $chengyy$