SPFA

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5000;
const int MAXM = 100000;
const int INF = 5000 * MAXM * 2 + 1; // 每条边长度不超过 5000
int n, m;
vector<pair<int, int>> e[MAXN + 5];
bool inQ[MAXN + 5];
int dis[MAXN + 5];  // 最短路
int dis2[MAXN + 5]; // 严格次短路
queue<int> q;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back({v, w});
        e[v].push_back({u, w});
    }
    for (int i = 1; i <= n; i++)
    {
        dis[i] = INF;
        dis2[i] = INF;
        inQ[i] = false;
    }
    dis[1] = 0;
    inQ[1] = true;
    q.push(1);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        inQ[u] = false;
        for (int i = 0; i < e[u].size(); i++)
        {
            int v = e[u][i].first;
            int w = e[u][i].second;
            // dis[u]+w < dis2[u]+w;
            if (dis[u] + w < dis[v])
            {
                // 更新最短路
                dis2[v] = dis[v];
                dis[v] = dis[u] + w;
                // SPFA
                if (!inQ[v])
                {
                    inQ[v] = true;
                    q.push(v);
                }
            }
            if (dis2[u] != INF &&
                dis2[u] + w < dis2[v] &&
                dis2[u] + w > dis[v])
            {
                // 次短路更新次短路
                dis2[v] = dis2[u] + w;
                // SPFA
                if (!inQ[v])
                {
                    inQ[v] = true;
                    q.push(v);
                }
            }
            if (dis[u] + w < dis2[v] &&
                dis[u] + w > dis[v])
            {
                // 最短路更新次短路
                dis2[v] = dis[u] + w;
                // SPFA
                if (!inQ[v])
                {
                    inQ[v] = true;
                    q.push(v);
                }
            }
        }
    }
    cout << dis2[n];
    return 0;
}

枚举严格次短路经过了哪条边

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5000;
const int MAXM = 100000;
const int INF = 5000 * MAXM * 2 + 1; // 每条边长度不超过 5000
int n, m;
vector<pair<int, int>> e[MAXN + 5];
priority_queue<pair<int, int>> pq;
bool vis[MAXN + 5];
// 1 为起点的最短路：dis[1][]
// n 为起点的最短路：dis[0][]
int dis[2][MAXN + 5];
// 求 s 为起点的最短路，存到 dis[idx][]
void dijkstra(int s, int idx)
{
    for (int i = 1; i <= n; i++)
    {
        dis[idx][i] = INF;
        vis[i] = false;
    }
    dis[idx][s] = 0;
    pq.push({-0, s});
    while (!pq.empty())
    {
        int u = pq.top().second;
        pq.pop();
        if (vis[u])
            continue;
        vis[u] = true;
        for (int i = 0; i < e[u].size(); i++)
        {
            int v = e[u][i].first;
            int w = e[u][i].second;
            if (dis[idx][u] + w < dis[idx][v])
            {
                dis[idx][v] = dis[idx][u] + w;
                pq.push({-dis[idx][v], v});
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back({v, w});
        e[v].push_back({u, w});
    }
    dijkstra(n, 0);
    dijkstra(1, 1);
    int minLen = dis[1][n];
    int ans = INF;
    for (int u = 1; u <= n; u++)
    {
        for (int i = 0; i < e[u].size(); i++)
        {
            int v = e[u][i].first;
            int w = e[u][i].second;
            int len = dis[1][u] + w + dis[0][v];
            if (len > minLen)
                ans = min(ans, len);
        }
    }
    cout << ans;
    return 0;
}