Roadblocks

解析

对于求次短路的问题，可以先回顾求序列中次大值的问题解法。

求序列中次大值，即先给最大值打擂台，如果原来的最大值给挤下去了，考虑原最大值是否可以更新次大值。如果没给挤下去，正常打擂台更新次大值。

这题的思路也一样。使用堆优化的 Dijkstra，从堆顶弹出元素时加入相邻元素，如果把最短路比下去了就更新最短路数组，把次短路设为原最短路。

更新次短路时，要注意次短路不能抢最短路的关键路径，需要加上判断 d[v]<dis+z。除此之外，正常更新次短路即可。

代码

​x
// the second shortest path
#include <bits/stdc++.h>
#define int long long
#define SIZE 20010
#define all(x) x.begin(), x.end()
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;

struct edge
{
    int u, w;   
};
vector<edge> a[SIZE];

int d[SIZE];
int d1[SIZE];
priority_queue<pair<int, int>> q;
void dijkstra(int sv)
{
    fill(d, d+SIZE, INT_MAX);
    fill(d1, d1+SIZE, INT_MAX);
    d[sv]=0;
    q.push({0, sv});
    while(!q.empty())
    {
        int dis=-q.top().first;
        int u=q.top().second; q.pop();
        for(auto w:a[u])
        {
            int v=w.u, z=w.w;
            if(d[v]>dis+z)
            {
                d1[v]=d[v];
                d[v]=dis+z;
                q.push({-d[v], v});
            }
            if(d1[v]>dis+z && d[v]<dis+z)
            {
                d1[v]=dis+z;
                q.push({-d1[v], v});
            }
        }
    }
}

signed main()
{
    int n, m, s=1, t;
    cin>>n>>m; t=n;
    for(int i=0; i<m; i++)
    {
        int u, v; cin>>u>>v;
        int w; cin>>w;
        a[u].push_back({v, w});
        a[v].push_back({u, w});
    }
    dijkstra(s);
    /*
    for(int i=1; i<=n; i++)
        cout<<d1[i]<<" ";
    cout<<endl;
    */
    cout<<d1[t];

    return 0;
}