题目地址：HDU 4725 这题卡了好长时间了，建图倒是会建，但是不会最短路的算法优化，本以为都需要堆去优化的，打算学了堆之后再来优化，但是昨晚CF的一道题。。（那题也是不优化过不了。。）然后我就知道了还有不需要堆也可以的优化，而且优化的操作很简单，把单向队列变成双端队列就行了。具体优化思路是若d[v]比队列前端的元素的距离小，就加入队列前端，否则加入队列尾端。很简单吧。。。会了后，把这题一加上

题目链接：https://cn.vjudge.net/problem/HDU-4725 题意：要求你建立一个奇怪的图，每一个点都在某一个层上，每一层上的点相互到达的权值为0，每一层可以到达相邻的两个层，权值为c，还有一些特殊的边可以链接不同层上的两个点，要求求第一个点到最后一个点的最短路。 题解：对于每一个点我们都要建立两个辅助点，然后每一层的相邻两个层连起来，最后把特殊边连起来，用优先队列+

- The Shortest Path in Nya Graph 核心思想,将每一层建立俩个辅助点,如图,让该层的所有点与这两个点相连,边权分别为c与0,就成功地把建边的时间复杂度大大缩小了,如图 AC代码 #include<iostream>#include<queue>#include<string>#include<string.h>#include<algori

我们根据每个人的layer把相同layer的人分配到同一个层次中。 然后记录走到每个层次的最小值。如果这个最小值被更新了， 那么我们就更新与这个层次相连的层次上的点。 其他的就是最普通的spfa求最短路了。 不过要用优先队列优化一下。 #include<stdio.h>#include<string.h>#include<stdlib.h>#include<iostream