求8.17京东笔试第三题解法

第三题回家过年
题目大致描述:n 个点、m 条边、期望路途长度 a。问:从点 1 到终点 n,长度为 a 的路径数有多少?

测试案例:
输入
3 6 2
1 2 1
1 2 1
1 2 1
2 3 1
2 3 1
2 3 1
输出:9

看大佬是用记忆化搜索或动态规划做的,菜鸡一开始也想到了 f(i, j) 表示点1 到 i,距离为 j 的方案数,但是没想通怎么处理循环路径(循环边会累加距离?),所以作罢。
交卷后想了想,感觉可以用 BFS,将遍历到的点相邻的点和到这些点的距离入队(距离大于 a 则跳过),好像也可以解决?
全部评论
DFS+记忆化,这题循环路径如果能走通的话应该算在答案里吧
点赞 回复 分享
发布于 2024-08-17 20:44 上海
bfs怎么做呢
点赞 回复 分享
发布于 2024-08-17 19:24 浙江
M
点赞 回复 分享
发布于 2024-08-17 18:59 上海
Bfs只能通过50%
点赞 回复 分享
发布于 2024-08-17 14:17 广东

相关推荐

11-19 18:44
已编辑
成都理工大学 Java
程序员花海:我面试过100+校招生,大厂后端面试不看ACM,竞赛经历含金量低于你有几份大厂实习 这个简历整体来看不错 可以海投
如何写一份好简历
点赞 评论 收藏
分享
11-23 15:14
中原工学院 Java
点赞 评论 收藏
分享
评论
3
2
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务