众所周知 dijkstra通常用来求单源最短路的问题 但是此题需要求 第二短路

我们只需要在dijkstra板子上略微修改 称之为--dijkstra扩展算法

通常我们会开一个dist数组来存放最短路径 同理 我们再开一个dist2数组来存放第二短路的路径

怎么得到第二短路？

我们通过比较 每次更新的距离 (以下简称该路径) 和 已经存在dist中的距离

1. 若该路径小于已知的最短路径 那么该路径为最短路径 而 最短路径为第二短路径 我们把他存放在dist2数组中
2. 若该路径大于已知的最短路径 并且小于该位置的第二段路径(如果有) 那么显然 我们把 该路径更新为第二短路径

如此 我们便得到了每个点的最短路径 同理 第n短路径也是可以求的

Code：

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <map>
#include <cstring>
#include <cmath>
#include <unordered_set>
#include <set>
#include <utility>
#include <climits>

#define int long long
#define PII pair<int, int> 
#define inf 0x3f
#define all(v) v.begin() , v.end()

using namespace std;
const int N = 1e6  + 10;

int e[N] , w[N] , ne[N] , h[N] , idx;
int n , m;
int dist[N] , dist2[N];
bool st[N];

//我比较习惯用链式前向星存图 因为他比较快 
void add(int a , int b , int c)
{
    e[idx] = b , w[idx] = c , ne[idx] = h[a] , h[a] = idx ++;
}

void dijkstra()
{    
    memset(dist , 0x3f , sizeof dist);
    memset(dist2 , 0x3f , sizeof dist2);
    dist[1] = 0;  //从哪里出发哪里就初始化为0

	//使用小根堆优化 时间复杂度可以减小到O(nlogm)
    priority_queue<PII , vector<PII> , greater<PII>> heap;
    heap.push({0 , 1});

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int distance = t.first , index = t.second;

        if (distance > dist2[index]) continue; //如果更新的距离已经比第二短路大了（如果有） 就没必要继续了

        for (int i = h[index] ; i != -1 ; i = ne[i])
        {
            int j = e[i];   
			
			//这是第一个判断因素
            if (dist[j] > distance + w[i])
            {
                dist2[j] = dist[j];
                dist[j] = distance + w[i];
                heap.push({dist[j] , j});
            }
			
			//这是第二个判断因素
            else if (distance + w[i] > dist[j] && distance + w[i] < dist2[j])
            {
                dist2[j] = distance + w[i];
                heap.push({dist2[j] , j});
            }
        }
    }    
}  

void solve()  
{   
    memset(h , -1 , sizeof h);
    
    cin >> n >> m;

    while (m -- )
    {
        int a , b , c;
        cin >> a >> b >> c;
        add(a , b , c);
        add(b , a , c);
    }

    dijkstra();

    cout << dist2[n] << endl;

}

signed main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    solve();
    return 0;
}

完结撒花！