2019-08-18 02:00 已编辑 中国科学院计算技术研究所 算法工程师
关注
全部评论
styik
清华大学 C++
睡醒想了一下第四题，正解应该是，先不考虑每天加的新边，建图，用dijkstra求每个点到终点的距离，复杂度nlogn。然后把这n个点放到一个数组，每个点对应一个位置，数值对应它到终点的距离。转化为不带修改的区间最大值查询问题：对q个询问，目的是在l,r区间中找到一个点能最大程度的减少s到终点的距离。那就是在l,r中，找一个区间最小值（离终点最近，每次查找复杂度logn），然后算从s直接到该点有没有缩短原来的最短距离（这个通过两者之前算的“与终点距离“可以得到）。整个算法nlogn
hasaki2
上海交通大学 算法工程师
建两张图，i->j 的有向边作为正图，j->i的逆边作为反图；这样正图一遍 dijistra 计算 1到其它点的最短路；反图一遍 dijistra 计算N到其它点的最短路； 每次的查询Q只用更新 d(1, i) + d(i, j) + d(j, N) 是否比 d(1, N) 短就行了
oi111 楼主
楼主 中国科学院计算技术研究所 算法工程师
有知道的吗？
鶸1318
华南理工大学 golang
题目是啥
王二22
上海交通大学 算法工程师
我觉得是有向加权图的最短路径问题，
oi111 楼主
楼主 中国科学院计算技术研究所 算法工程师
感觉应该是Dijkstra计算最短路（优先队列优化），然后用rmq进行查询。但来不及写，不知道有没有ac的?
oi111 楼主
楼主 中国科学院计算技术研究所 算法工程师
nbShawnLu
电子科技大学 算法工程师
应该是先dijkstra一次，记录路径，然后每一次查询都沿着这个路径寻找能不能短接？每天沿着路径，看看特惠起点后续每一点在不在终点范围内，把最大的累计值和p比较，这样的话复杂度就是o(n^2+qn)了。
字节跳动靠谱内推
字节跳动_游戏中台_算法数据
另求大佬告知第二题应该怎么做，用dfs和bfs测试样例第二部分都无法通过
字节跳动靠谱内推
字节跳动_游戏中台_算法数据
第三题解法，用dijkstra在和特殊航道的路径进行比较，考完以后再做的，测试数据能ac，不知道考试的能过多少....
styik
清华大学 C++
在这么短时间的考试内放一道这种题，太凶残。rmq的各种方法自己手写的话本来就超容易手残写错。如果我来写的话，建图，dijkstra，线段树，估计代码奔着150行去了。
HPlus
华中科技大学 C++
为什么我建立邻接矩阵，就说超内存了。
相关推荐
11-13 15:20
门头沟学院 前端工程师 
点赞 评论 收藏
分享