08-17 13:52 门头沟学院 Java 发布于上海
关注
求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 则跳过），好像也可以解决？
题目大致描述：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 则跳过），好像也可以解决？
全部评论
无助的缄默
合肥工业大学 Java
Bfs只能通过50%
踏实的乌龟说我这儿没问题啊
上海大学 C++
M
timeErrors
南京大学 Java
bfs怎么做呢
云月来
门头沟学院 Java
DFS+记忆化，这题循环路径如果能走通的话应该算在答案里吧
相关推荐
大疆公司氛围 166人发布 
Spark-：欢迎大佬加入腾讯莞工俱乐部，有空可以一起吃饭，入职后找charlexchen他是俱乐部话事人
开玩笑的，恭喜大佬拿到腾讯offer，teg是个很nice的bg回想两年前入职鹅子也跟大佬一样的心情，可惜两年时间能改变太多导致已经润了，祝大佬在腾讯过的开心愉快 点赞 评论 收藏
分享
11-01 08:48
门头沟学院 C++ 
点赞 评论 收藏
分享
