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++
为什么我建立邻接矩阵，就说超内存了。
相关推荐
投递淘天集团等公司10个岗位 > 点赞 评论 收藏
分享
Yushuu：你的确很厉害，但是有一个小问题：谁问你了？我的意思是，谁在意？我告诉你，根本没人问你，在我们之中0人问了你，我把所有问你的人都请来 party 了，到场人数是0个人，誰问你了？WHO ASKED？谁问汝矣？誰があなたに聞きましたか？누가 물어봤어？我爬上了珠穆朗玛峰也没找到谁问你了，我刚刚潜入了世界上最大的射电望远镜也没开到那个问你的人的盒，在找到谁问你之前我连癌症的解药都发明了出来，我开了最大距离渲染也没找到谁问你了我活在这个被辐射蹂躏了多年的破碎世界的坟墓里目睹全球核战争把人类文明毁灭也没见到谁问你了😆 点赞 评论 收藏
分享
11-20 13:35
广东白云学院 数据运营 
立马来offer：去哪个大厂了啊，其实你选了小公司，遇到不开心的也会后悔没有选择大平台。别美化小公司了，至少大厂有平台，有二次选择的能力 点赞 评论 收藏
分享