拉格朗日插值

dij原来的写法请移步这里首先，让我们举一个洛谷中的情境这题中，我们可以二分mid答案，小于等于mid的边权是0，大于的是1，再计算最短路是否<=k；那么在这样边权只有0和1的时候，dij算法是否可以优化呢？可以（不然我写这篇blog干嘛）不必再使用优先队列，而只需要一个双段队列deque就可以解决做法做法就是一样每次取出队首，然后每次更新从它延伸出去的那条路权是1就放队尾，权是0就放队首其