次短路

次短路就是第二短的路，用双数组法好用

步骤：

1.开d1[N] d2[N]两个数组分别以1节点和n节点作为源点spfa，注意清空数组队列啥的

2.很重要的一句话：对于[u,v]这条边和两个节点，起点到u的最短路与终点到v的最短路和[u,v]这边的边权，三者的和即为次短路。

这个和要大于最短路d1[n]的基础上,迭代找最小的。

例题：

道路障碍

代码

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int>P;
const int N=1e5+10,M=0x3f3f3f3f;
vector<P>g[N];
int n,m,d1[N],d2[N];
bool st[N];
void spfa1()
{
    memset(d1,0x3f,sizeof d1);
    queue<int>q;
    d1[1]=0;
    q.push(1);
    st[1]=true;
    while(q.size())
    {
        int t=q.front();
        q.pop();
        st[t]=false;
        for(auto &w:g[t])
        {
          if(d1[w.x]>d1[t]+w.y)
          {
            d1[w.x]=d1[t]+w.y;
            if(!st[w.x])
            {
                q.push(w.x);
                st[w.x]=true;
            }
          }
        }
    }

}
void spfa2()
{
    memset(d2,0x3f,sizeof d2);
    memset(st,false,sizeof st);
    queue<int>q;
    d2[n]=0;
    q.push(n);
    st[n]=true;
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        st[t]=false;
        for(auto &w:g[t])
        {
            if(d2[w.x]>d2[t]+w.y)
            {
                d2[w.x]=d2[t]+w.y;
                if(!st[w.x])
                {
                    q.push(w.x);
                    st[w.x]=true;
                }
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a].push_back({b,c});
        g[b].push_back({a,c});
    }
    spfa1();
    spfa2();
    int ans=M;
    for(int i=1;i<=n;i++)
    {
        for(auto &w:g[i])
        {
            int tmp=d1[i]+d2[w.x]+w.y;
            if(tmp>d1[n]&&tmp<ans)
            {
                ans=tmp;
            }
        }
    }
    printf("%d",ans);
    return 0;
}