styik
2019-08-18 18:11 清华大学 C++
关注
睡醒想了一下第四题，正解应该是，先不考虑每天加的新边，建图，用dijkstra求每个点到终点的距离，复杂度nlogn。然后把这n个点放到一个数组，每个点对应一个位置，数值对应它到终点的距离。转化为不带修改的区间最大值查询问题：对q个询问，目的是在l,r区间中找到一个点能最大程度的减少s到终点的距离。那就是在l,r中，找一个区间最小值（离终点最近，每次查找复杂度logn），然后算从s直接到该点有没有缩短原来的最短距离（这个通过两者之前算的“与终点距离“可以得到）。整个算法nlogn
查看原帖
点赞 评论
相关推荐
投递谷歌等公司10个岗位 >
牛客84762733号：3月份吧，没有offer的我感觉时间过得很漫长
点赞 评论 收藏
分享
10-30 21:46
安庆职业技术学院 后期制作 
点赞 评论 收藏
分享
牛客热帖
正在热议
# 25届秋招总结 #
323633次浏览 3010人参与
# 上班苦还是上学苦呢？ #
70185次浏览 627人参与
# 百度开奖 #
180815次浏览 1132人参与
# 地方国企笔面经互助 #
4420次浏览 12人参与
# 如果有时光机，你最想去到哪个年纪？ #
20841次浏览 370人参与
# 选完offer后，你后悔学本专业吗 #
21610次浏览 158人参与
# 阿里云管培生offer #
36501次浏览 421人参与
# 我的实习求职记录 #
6067860次浏览 83523人参与
# 如何一边实习一边秋招 #
996053次浏览 12661人参与
# 入职第一天，你准备什么时候下班 #
21520次浏览 144人参与
# 招聘要求与实际实习内容不符怎么办 #
10696次浏览 276人参与
# bilibili求职进展汇总 #
32945次浏览 354人参与
# 许愿池 #
214595次浏览 2534人参与
# 学历or实习经历，哪个更重要 #
53599次浏览 419人参与
# 实习工作，你找得还顺利吗？ #
247603次浏览 2905人参与
# 海康威视求职进展汇总 #
400449次浏览 3408人参与
# 通信硬件薪资爆料 #
607884次浏览 5154人参与
# 携程求职进展汇总 #
135439次浏览 928人参与
# 正在实习的你，几点下班 #
53025次浏览 395人参与
# 工作两年想退休了 #
52990次浏览 672人参与
# 如果再来一次，你还会学硬件吗 #
95122次浏览 1169人参与
# 软件开发薪资爆料 #
2193643次浏览 21881人参与