求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 则跳过),好像也可以解决?
全部评论
Bfs只能通过50%
M
bfs怎么做呢
DFS+记忆化,这题循环路径如果能走通的话应该算在答案里吧
相关推荐
09-25 16:15
武汉科技大学 电化学工程师 牛客307226505号:现在一般单9单2进工艺岗,秋招就是10%的人拿80%的offer,你投的企业 那些 99 29的 佬也都在投,等他们十月份签了三方 把手里的oc释放出来就好点了
点赞 评论 收藏
分享