牛客oi测试赛 二 B 路径数量

时间：2023-03-08 20:41:23

题目描述

给出一个 n * n 的邻接矩阵A.
A是一个01矩阵 .
A[i][j]=1表示i号点和j号点之间有长度为1的边直接相连.
求出从 1 号点 到 n 号点长度为k的路径的数目.

输入描述:

第1行两个数n,k (20 ≤n ≤ 30,1 ≤ k ≤ 10)
第2行至第n+1行，为一个邻接矩阵

输出描述:

题目中所求的数目

输入例子:
4 2

0 1 1 0

1 0 0 1

1 0 0 1

0 1 1 0
输出例子:
2

-->

示例1

输入

复制

4 2

0 1 1 0

1 0 0 1

1 0 0 1

0 1 1 0

输出

复制

2

说明

牛客oi测试赛 二 B 路径数量
样例如图:
第一条路径：1-2-4
第二条路径：1-3-4
题意：求出这个图的1-n走正好k步的路径条数，点可以重复走
思路：首先我想的是搜索，但是很明显会TLE，我们看这个数据范围只有30,一般数据范围比较小，搜索T了的情况，我们就使用dp
现在我们想下怎么得到我们想要的递推式呢
我们列出题目的要求
1.可以重复走
2.正好走k步
因为我们每一点都有不同的步数
例如：
牛客oi测试赛 二 B 路径数量

1-2   1-2-3-2

到2的步数都是不同的

所以我们要枚举步数的情况

#include<cstdio>

#include<cstring>

int a[][];

long long f[][];

int main()

{

    f[][]=;

    int n,k;

    scanf("%d%d",&n,&k);

    for(int i=;i<=n;++i)

        for(int j=;j<=n;++j)

            scanf("%d",&a[i][j]);

    for(int i=;i<=k;++i)

        for(int j=;j<=n;++j)

            for(int t=;t<=n;++t)

                if(a[j][t])//如果 j到t 有一条路 如果当前我们走到j点是x步，那么我们只要把t点的x+1步的值加上当前的j点的值即可

                    f[t][i]+=f[j][i-];

    printf("%lld\n",f[n][k]);

    return ;

}

相关文章