洛谷2865 路障Roadblocks

题意

给一个无向图，求严格次小最短路。

其中点数 $N\le 5000$ ，边数 $R\le 100000$ 。

题解

在跑最短路的时候维护一个次短路即可。

具体做法是每次枚举的边权先与最短路比较，将较小值给最短路，较大值再与次短路比较。

剪枝是如果当前枚举的边比次短路还大就退出。

需要注意的是不能用 $vis[]$ 数组来进行判重，可能是因为次短路的缘故不只跑一次吧。

#include<bits/stdc++.h>
#define pr pair<int,int>
#define mp make_pair

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

struct Edge {
    int next,to,w;
} edge[200005];
int cnt,head[5005],n,m,a,b,c,dis[5005],dis2[5005];

inline void add(int u,int v,int w)
{
    edge[++cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

inline void dijkstra()
{
    memset(dis,0x3f,sizeof(dis));
    memset(dis2,0x3f,sizeof(dis2));
    dis[1]=0;
    priority_queue <pr,vector<pr>,greater<pr> > q;
    q.push(mp(0,1));
    while (!q.empty())
    {
        int x=q.top().second,d=q.top().first; q.pop();
        if (d>dis2[x]) continue;
        for (int i=head[x];i;i=edge[i].next)
        {
            int y=edge[i].to,d2=edge[i].w+d;
            if (d2<dis[y])
            {
                swap(dis[y],d2);
                q.push(mp(dis[y],y));
            }
            if (d2<dis2[y] && d2>dis[y])
            {
                dis2[y]=d2;
                q.push(mp(dis2[y],y));
            }
        }
    }
    printf("%d",dis2[n]);
}

int main()
{
    n=read(); m=read();
    for (int i=1;i<=m;i++)
    {
        a=read(); b=read(); c=read();
        add(a,b,c);
        add(b,a,c);
    }
    dijkstra();
    return 0;
}