关注
睡醒想了一下第四题,正解应该是,先不考虑每天加的新边,建图,用dijkstra求每个点到终点的距离,复杂度nlogn。然后把这n个点放到一个数组,每个点对应一个位置,数值对应它到终点的距离。转化为不带修改的区间最大值查询问题:对q个询问,目的是在l,r区间中找到一个点能最大程度的减少s到终点的距离。那就是在l,r中,找一个区间最小值(离终点最近,每次查找复杂度logn),然后算从s直接到该点有没有缩短原来的最短距离(这个通过两者之前算的“与终点距离“可以得到)。整个算法nlogn
查看原帖
点赞 评论
相关推荐
11-25 17:03
门头沟学院 Java 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 为了去实习,我赌上了___ #
18693次浏览 196人参与
# 摸鱼被leader发现了怎么办 #
70625次浏览 407人参与
# 百融云创求职进展汇总 #
154次浏览 0人参与
# uu们,春招你还来吗? #
10913次浏览 79人参与
# 2025年终总结 #
11432次浏览 204人参与
# 哪一瞬间让你觉得“这班不如不上” #
10227次浏览 144人参与
# 父母对你找工作是助力还是阻力? #
12637次浏览 192人参与
# 如果可以,你希望哪个公司来捞你 #
154687次浏览 650人参与
# 降低公积金和取消房补怎么选 #
23318次浏览 79人参与
# 工作中哪个瞬间让你想离职 #
109296次浏览 771人参与
# 十二月请对我好一点 #
23649次浏览 326人参与
# 高薪高压 vs 低薪wlb,你怎么选? #
9950次浏览 110人参与
# 一人推荐一个值得做的项目 #
8354次浏览 115人参与
# 运营每日一题 #
112603次浏览 885人参与
# 第一份工作能做外包吗? #
85743次浏览 574人参与
# 这些公司卡简历很严格 #
80187次浏览 366人参与
# 硬件人的简历怎么写 #
317058次浏览 3063人参与
# 工作前VS工作后,你的心态变化 #
12402次浏览 151人参与
# 学历or实习经历,哪个更重要 #
201852次浏览 1068人参与
# 秋招提前批启动你开冲了吗 #
160656次浏览 2244人参与
# 工作中出现了XX情况正常吗 #
30406次浏览 208人参与

曼迪匹艾公司福利 114人发布