腾讯笔试第四题（飞机航线那题）怎么做？

睡醒想了一下第四题，正解应该是，先不考虑每天加的新边，建图，用dijkstra求每个点到终点的距离，复杂度nlogn。然后把这n个点放到一个数组，每个点对应一个位置，数值对应它到终点的距离。转化为不带修改的区间最大值查询问题：对q个询问，目的是在l,r区间中找到一个点能最大程度的减少s到终点的距离。那就是在l,r中，找一个区间最小值（离终点最近，每次查找复杂度logn），然后算从s直接到该点有没有缩短原来的最短距离（这个通过两者之前算的“与终点距离“可以得到）。整个算法nlogn

建两张图，i->j 的有向边作为正图，j->i的逆边作为反图；这样正图一遍 dijistra 计算 1到其它点的最短路；反图一遍 dijistra 计算N到其它点的最短路； 每次的查询Q只用更新 d(1, i) + d(i, j) + d(j, N) 是否比 d(1, N) 短就行了

有知道的吗？

题目是啥

我觉得是有向加权图的最短路径问题，

感觉应该是Dijkstra计算最短路（优先队列优化），然后用rmq进行查询。但来不及写，不知道有没有ac的?

应该是先dijkstra一次，记录路径，然后每一次查询都沿着这个路径寻找能不能短接？每天沿着路径，看看特惠起点后续每一点在不在终点范围内，把最大的累计值和p比较，这样的话复杂度就是o(n^2+qn)了。

另求大佬告知第二题应该怎么做，用dfs和bfs测试样例第二部分都无法通过

第三题解法，用dijkstra在和特殊航道的路径进行比较，考完以后再做的，测试数据能ac，不知道考试的能过多少....

在这么短时间的考试内放一道这种题，太凶残。rmq的各种方法自己手写的话本来就超容易手残写错。如果我来写的话，建图，dijkstra，线段树，估计代码奔着150行去了。

为什么我建立邻接矩阵，就说超内存了。