首页 > 逛公园
开通博客写题解
头像 hnust_yangyanjun
发表于 2021-04-23 20:39:55
题意：有一个n个节点，m条有向边的图，如果从1到n的最短路为d，请你求从1到n的路线长度小于d+k的数目，答案对p取模。 思路：最短路+记忆化搜索反向建图求每一个节点到n节点的最短距离。定义状态dp[i][j]为从节点i，还可以额外多走j的长度的状态到目标状态( dp[n][ji] (k>=j 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 jzdx（hjh）
发表于 2021-04-20 22:05:31
题号 NC16416名称 逛公园来源 NOIP2017提高组复赛 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld题目描述 策策同学特别喜欢逛公园。 公园可以看成一张 N 个点 M 条边构成的有向图，且 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 sunrise__sunrise
发表于 2021-04-15 17:14:58
题目大意 组输入，每次有个点条边的有向图。首先如果从起点不能到达终点，那么输出一个，如果可以到达求解出最短路的距离记录为。那么我在保证最多另外让你走个距离的情况下，问你从起点到终点的方式有几种？并且方案数要对取模。因为我们存在边权为的边，所以如果有一个环它的权值和都是，那么直接输出。 Solutio 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 在刷题的单身狗很开心
发表于 2023-11-16 14:45:17
本题要求求路径数，图论的最短路算法可求不了路径数，那么可以想到在图里面使用动态规划的方式去求路径数。 在本题里面可以得出从某一点到下一点的路径方式有多少取决去这一点之前的路径数，以及该点和下一点的路径数。 那么就可以知道之间可以使用动态规划去求解。 但本题有要求路径长度不能超过n+ 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 savage
发表于 2019-09-02 23:33:47
题目描述 策策同学特别喜欢逛公园。 公园可以看成一张 N 个点 M 条边构成的有向图，且没有自环和重边。其中 1 号点是公园的入口， N 号点是公园的出口，每条边有一个非负权值，代表策策经 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”