【每日一题】7月7日题目精讲—最短路

题号 NC19814
名称 最短路
来源 牛客国庆集训派对Day6
戳我进入往期每日一题汇总贴~
往期每日一题二期题单

图片说明

如果你在题库做题时遇到了喜欢的题目,欢迎推荐给邓老师~ 点击查看详情

题解

求任意两点最短路,但是点数很多。
比已知模型多的东西才是解题的关键——看看除了最短路还有什么条件:边长是1,这个暂时没有什么用;1≤m≤n+100——边数没有比点数多太多,也就是说,最终的图是一棵树上面加上少量的边。
先忽略加上的那些边如果这只是一棵树,维护出每个点的深度然后求lca即可。
现在考虑如果有这些多余的边怎么办?或者说这些多余的边i到j在什么情况下影响x到y的答案?显然是i->j的最短路就是i->j这条边,而非树上的边,这样dis[x->y] = dis[x->i]+dis[i->j]+dis[j->y]
这样去枚举ij的话会超时,其实枚举其中一个就可以了,即dis[x->y] = dis[x->i]+dis[i->y] (i->j的距离在i->y中自然会选择性更新),即我们可以用以100条边的每一条边的v任意一个顶点为起点做一个dfs,把dis数组维护出来。最后把上述结果的最小值和直接在树上走比较一下即可。

活动奖励:

在牛客博客中写出题解,并回复地址
审核通过可获得(依据题目难度和题解的内容而定)

本道题目7月14日中午12:00之前写的题解有获得牛币资格~

【特别介绍】每日一题交流群,群内定期有福利发放,群号:659028468

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客:https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能:进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议:牛客博客意见反馈专贴

全部评论
https://blog.nowcoder.net/n/c3bc34a0891e4553b02014e1d38ba526
点赞 回复 分享
发布于 2020-08-17 14:03
https://blog.nowcoder.net/n/6ddcb851129743fab450f499f489df30
点赞 回复 分享
发布于 2020-07-29 09:27
https://blog.nowcoder.net/n/76a3f4fb948e4b85beb00546a0e9354c
点赞 回复 分享
发布于 2020-07-28 20:24
https://blog.nowcoder.net/n/7eb7a8167556421d8bebd35e555b7916
点赞 回复 分享
发布于 2020-07-14 22:30
https://blog.nowcoder.net/n/00c7c4afce4b487b895b64599554f2c8
点赞 回复 分享
发布于 2020-07-13 17:27
https://blog.nowcoder.net/n/83aba0bda86b4a80aed790f8f445a7fd
点赞 回复 分享
发布于 2020-07-10 23:32
https://blog.nowcoder.net/n/fa250993e59d475ead1d33475d306793
点赞 回复 分享
发布于 2020-07-10 12:10
https://blog.nowcoder.net/n/278179d9508248fbae1948d466bdeddd
点赞 回复 分享
发布于 2020-07-09 15:24
https://blog.nowcoder.net/n/1fe4b32399f54c3f9db661046f7d52b6
点赞 回复 分享
发布于 2020-07-08 15:29
https://blog.nowcoder.net/n/f6d7ab38e2c7420ab884231cac0da66a
点赞 回复 分享
发布于 2020-07-08 14:33
https://blog.nowcoder.net/n/4cd3e675efe44f01931c6cd9272b51ac
点赞 回复 分享
发布于 2020-07-07 15:37
https://blog.nowcoder.net/n/9e97d71615b14e9b97571f08fdc97f17
点赞 回复 分享
发布于 2020-07-07 00:31
https://blog.nowcoder.net/n/f21a4074583443619928a8661017dbeb
点赞 回复 分享
发布于 2020-07-06 20:01
https://blog.nowcoder.net/n/33393057dc9a4e939e154b5dcad799ad
点赞 回复 分享
发布于 2020-07-06 17:18
https://blog.nowcoder.net/n/7353e7a20a194775bb5e50669deb2b18
点赞 回复 分享
发布于 2020-07-06 13:23

相关推荐

2025-12-24 15:25
已编辑
门头沟学院 前端工程师
是腾讯的csig腾讯云,前天晚上九点突然打电话约面,激动的通宵学了一晚上,第二天状态很差改了今天(以后再也不通宵学习了)感觉自己浪费了面试官一个半小时单纯手写+场景,无八股无项目无算法,打击真的很大,全是在面试官提醒的情况下完成的,自己技术方面真的还是有待提高,实力匹配不上大厂和已经面试的两个公司完全不一样,很注重编码能力和解决问题的能力,然而我这两个方面都很薄弱,面试官人很好很耐心的等我写完题目,遇到瓶颈也会提醒我,写不出题也会很耐心的跟我讲解好感动,到最后面试结束还安慰我打算把下周最后一场面试面完之后就不面啦,如果能去实习还是很开心,但是最重要的还是好好努力提高技术以下是面经第一题// 实现一个解析 url 参数的函数function parseUrl(urlStr) {// TODO}parseUrl('*********************************************');// 返回 {a: 1, b: 2, c: 3}追问:在链接里见过什么部分?用 hash 路由的话放在哪第二题// 考虑有一个异步任务要执行,返回 Promise,这个任务可能会失败,请实现 retry 方法,返回新方法,可以在失败后自动重试指定的次数。/*** 异步任务重试* @param task 要执行的异步任务* @param times 需要重试的次数,默认为 3 次*/function retry(task, times = 3) {// TODO: 请实现}// ---------------测试示例 ----------------// 原方法const request = async (data) => {// 模拟失败if (Math.random() < 0.7) {throw new Error('request failed');}const res = await fetch('https://jsonplaceholder.typicode.com/posts', {method: 'POST',body: JSON.stringify(data),});return res.json();}// 新的方法const requestWithRetry = retry(request);// 使用async function run() {const res = await requestWithRetry({ body: 'content' });console.log(res);}run();第三题就是给 retry 函数添加类型注释,用到泛型第四题:在组件库中将 Alert 用 api 的形式实现(应该就是 message 这个组件)怎么渲染到一个浮层里而不是原地渲染出来
不知道怎么取名字_:技术这个东西,太杂了,而且要下功夫的
查看5道真题和解析
点赞 评论 收藏
分享
2025-11-14 16:15
已编辑
湖南工业大学 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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