BZOJ-1726: [Usaco2006 Nov]Roadblocks第二短路

Description

求第二短路。要求小于最短路。n<=5000,m<=100000

堆优化dij，然后和求k短路类似，将评判标准变为初选过两次不同的单源路径长度。出堆的时候判断一下就行了。

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,ans=-1;
int head[5100],to[201000],nxt[201000],f[201000],cnt,num[5100],dis[5100];
void add(int x,int y,int z)
{
    to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z;
}
struct node {int id,dis;};
bool operator<(node x,node y){return x.dis>y.dis;}
priority_queue<node>q;
int main()
{
    scanf("%d%d",&n,&m);
    int i,x,y,z;
    for(i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z); add(y,x,z);
    }
    q.push((node){1,0});
    while(1)
    {
        x=q.top().id; y=q.top().dis; q.pop();
        if(y>dis[x]) num[x]++,dis[x]=y;
        if(x==n)
        {
            if(ans==-1) ans=y;
            else if(ans!=y) {ans=y; break;}
        }
        if(num[x]<=2)
            for(int i=head[x];i;i=nxt[i])
                q.push((node){to[i],y+f[i]});
    }
    printf("%d",ans);
    return 0;
}