styik
2019-08-18 18:11 清华大学 C++
关注
睡醒想了一下第四题，正解应该是，先不考虑每天加的新边，建图，用dijkstra求每个点到终点的距离，复杂度nlogn。然后把这n个点放到一个数组，每个点对应一个位置，数值对应它到终点的距离。转化为不带修改的区间最大值查询问题：对q个询问，目的是在l,r区间中找到一个点能最大程度的减少s到终点的距离。那就是在l,r中，找一个区间最小值（离终点最近，每次查找复杂度logn），然后算从s直接到该点有没有缩短原来的最短距离（这个通过两者之前算的“与终点距离“可以得到）。整个算法nlogn
查看原帖
点赞 评论
相关推荐
牛客热帖
更多
正在热议
更多
# 哪些公司开春招了？ #
5239次浏览 94人参与
# 实习教会我的事 #
50359次浏览 390人参与
# 上班以后，你还有哪些坚持的爱好？ #
4766次浏览 140人参与
# 为了实习逃课值吗？ #
61550次浏览 516人参与
# 你都在哪些场所面过试？ #
13035次浏览 183人参与
# 拼多多工作体验 #
43914次浏览 283人参与
# 工作压力大怎么缓解 #
135177次浏览 1197人参与
# AI coding的好用工具分享 #
11754次浏览 278人参与
# 实习怎么做才有更好的产出 #
7868次浏览 167人参与
# 找工作以来，你最看不惯__ #
7347次浏览 194人参与
# 实习生工资多少才算正常？ #
8908次浏览 168人参与
# 你最近因为什么迷茫？ #
24658次浏览 390人参与
# 实习离职怎么跟领导说 #
75158次浏览 418人参与
# 你给AI提过哪些离谱的需求？ #
4087次浏览 139人参与
# 工作一周年分享 #
49495次浏览 251人参与
# 领导做过最不靠谱的事 #
8256次浏览 167人参与
# 牛客AI文生图 #
19161次浏览 225人参与
# xxx岗位的一天 #
41534次浏览 275人参与
# 实习学不到东西怎么办？ #
270793次浏览 2491人参与
# 机械/制造每日一题 #
84416次浏览 1440人参与