Dijkstra次短路

Dijkstra次短路

其实就是带入两个变量进行增广,一个表示最短,一个表示次短。
接下来讲一下如何用堆维护,每当更新到了最短或次短,就将这个答案put进堆里就可以了。堆的大小不是很清楚,建议用调优先队列。

例题

传送门

代码如下

#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=5005,MAXM=1e5+5;
int n,m,len,Ans=1e9,MAX=1e9,dst[2][MAXN];
struct Edge{
    int tot,lnk[MAXN],nxt[MAXM<<1],son[MAXM<<1],W[MAXM<<1];
    void Add(int x,int y,int w){nxt[++tot]=lnk[x];lnk[x]=tot;son[tot]=y,W[tot]=w;}
}E;
int read(){
    int ret=0;char ch=getchar();bool f=1;
    for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');
    for(; isdigit(ch);ch=getchar()) ret=(ret<<1)+(ret<<3)+ch-48;
    return f?ret:-ret;
}
struct xcw{
    int x,id;
    bool operator <(const xcw b)const{return x>b.x;}
}hep[MAXM];
void put(int x,int id){hep[++len]=(xcw){x,id};push_heap(hep+1,hep+1+len);}
xcw get(){pop_heap(hep+1,hep+1+len);return hep[len--];}
void DIJ(){
    memset(dst,63,sizeof(dst));put(0,1);dst[0][1]=0;
    while(len){
        xcw OUT=get();
        int k=OUT.id,MIN=OUT.x;
        if(dst[1][k]<MIN) continue;
        for(int j=E.lnk[k];j;j=E.nxt[j]){
            int Now=MIN+E.W[j];
            if(dst[0][E.son[j]]>Now) swap(dst[0][E.son[j]],Now),put(dst[0][E.son[j]],E.son[j]);
            if(dst[1][E.son[j]]>Now&&Now>dst[0][E.son[j]]) swap(dst[1][E.son[j]],Now),put(dst[1][E.son[j]],E.son[j]);
        }
    }
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("prob.in","r",stdin);
    freopen("prob.out","w",stdout);
    #endif
    n=read(),m=read();
    for(int i=1,x,y,w;i<=m;i++) x=read(),y=read(),w=read(),E.Add(x,y,w),E.Add(y,x,w);
    DIJ();
    printf("%d\n",dst[1][n]);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部