c++用dijkstra堆优化版求严格次短路（洛谷p2865）acwing（Tle）版本

先看原题：

贝茜把家搬到了一个小农场，但她常常回到 FJ 的农场去拜访她的朋友。贝茜很喜欢路边的风景，不想那么快地结束她的旅途，于是她每次回农场，都会选择第二短的路径，而不象我们所习惯的那样，选择最短路。
贝茜所在的乡村有 R(1\le R \le 10^5)R(1≤R≤105) 条双向道路，每条路都联结了所有的 N(1\le N\le 5000)N(1≤N≤5000) 个农场中的某两个。贝茜居住在农场 11，她的朋友们居住在农场 NN（即贝茜每次旅行的目的地）。
贝茜选择的第二短的路径中，可以包含任何一条在最短路中出现的道路，并且，一条路可以重复走多次。当然咯，第二短路的长度必须严格大于最短路（可能有多条）的长度，但它的长度必须不大于所有除最短路外的路径的长度。

输出样例：

4 4
1 2 100
2 4 200
2 3 250
3 4 100

输出样例：

450

Two routes: 1 -> 2 -> 4 (length 100+200=300) and 1 -> 2 -> 3 -> 4 (length 100+250+100=450)

代码如下：

#include
#include
#include
 
using namespace std;
 
typedef pair<int, int> PII;
 
const int N = 1e3 + 10, M = 2e5 + 10;
 
int n, m;
int dist1[N], dist2[N];
int h[N], w[M], e[M], ne[M], idx;
 
struct Ver
{
    int to, di;
    bool operator< (const Ver &W) const
    {
        return di > W.di;
    }
};
 
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx;
}
 
int dijkstra()
{
    memset(dist1, 0x3f, sizeof dist1);
    memset(dist2, 0x3f, sizeof dist2);
 
    priority_queue, greater> heap;
    
    heap.push({0, 1});
    dist1[1] = 0;
    
    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();
        
        int ver = t.second, distance = t.first;
        
        if(distance > dist2[ver]) continue;
        
        for(int i =h[ver]; i != -1; i = ne[i])
        {
            int j =e[i];
            
            if(dist1[j] > distance + w[i])
            {
                dist2[j] = dist1[j];
                dist1[j] = distance + w[i];
                heap.push({dist1[j], j});
            }
            else if(dist2[j] > distance + w[i] && distance + w[i] > dist1[j])
            {
                dist2[j] = distance + w[i];
                heap.push({dist2[j], j});
            }
        }
    }
    return dist2[n];
}
 
int main()
{
    scanf("%d%d", &n, &m);
 
    memset(h, -1, sizeof h);
 
    while (m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }
 
    printf("%d\n", dijkstra());
 
    return 0;
}

1、有双向边，所以建图的时候要注意

2、初始化链表

3、使用结构体存储出发点和距离

4、初始化最短路和次短路的数组

5、要是实际距离比次短路都要长，就不加入队列中去

6、最重要的一步

      要是当前新加入的点比最短路还要短，就先吧次短路更新为当前的最短路，再把最短路更新， 

      这样就不会出错了，如果新加入的点比次短路短但是比最短路长，更新次短路

要是有在acwing学习的友友们知道怎么优化，麻烦评论以下了