最短路

luckydrawbox · 2022-08-28 21:36:41 · 个人记录

Floyd

变量

函数

代码

void Floyd(int n,int *a){
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
}

Dijkstra

变量

函数

代码

int d[N],v[N];
void Dijkstra(int s){
    memset(d,0x3f,sizeof(d));
    memset(v,0,sizeof(v));
    d[s]=0;
    priority_queue<pair<int,int> >q;
    q.push(make_pair(0,s));
    while(q.size()){
        int x=q.top().second;
        q.pop();
        if(v[x])
            continue;
        v[x]=1;
        for(int i=head[x];i;i=nxt[i]){
            int y=ver[i],z=edge[i];
            if(d[y]>d[x]+z){
                d[y]=d[x]+z;
                q.push(make_pair(-d[y],y));
            }
        }
    }
}

SPFA+负环

变量

函数

代码

int d[N],cnt[N];
bool v[N];
bool spfa(int s){
    memset(d,0x3f,sizeof(d));
    memset(v,0,sizeof(v));
    memset(cnt,0,sizeof(cnt));
    queue<int>q;
    d[s]=0;
    v[s]=1;
    q.push(s);
    while(q.size()){
        int x=q.front();
        q.pop();
        v[x]=0;
        cnt[x]++;
        if(cnt[x]>n)
            return 1;
        for(int i=head[x];i;i=nxt[i]){
            int y=ver[i],z=edge[i];
            if(d[y]>d[x]+z){
                d[y]=d[x]+z;
                if(!v[y]){
                    q.push(y);
                    v[y]=1;
                }
            }
        }
    }
    return 0;
}

Johnson 全源最短路

变量

函数

代码

struct Johnson{
    int head[N],ver[M<<1],nxt[M<<1],tot=1;
    int vis[N],in[N];
    ll edge[M<<1],h[N],d[N];
    void add(int x,int y,ll z){
        ver[++tot]=y,edge[tot]=z,nxt[tot]=head[x],head[x]=tot;
    }
    bool spfa(int s){
        queue<int>q;
        memset(h,0x3f,sizeof(h));
        memset(vis,0,sizeof(vis));
        memset(in,0,sizeof(in));
        h[s]=0;vis[s]=1;q.push(s);
        while(q.size()){
            int x=q.front();q.pop();
            vis[x]=0;
            for(int i=head[x];i;i=nxt[i]){
                int y=ver[i];
                if(h[y]>h[x]+edge[i]){
                    h[y]=h[x]+edge[i];
                    if(!vis[y]){
                        vis[y]=1;in[y]++;
                        q.push(y);
                        if(in[y]==n+1)return 0;
                    }
                }
            }
        }
        return 1;
    }
    void dijkstra(int s){
        priority_queue<pair<ll,int> >q;
        memset(d,0x3f,sizeof(d));
        for(int i=1;i<=n;i++)d[i]=1e9;
        memset(vis,0,sizeof(vis));
        q.push(make_pair(d[s]=0,s));
        while(q.size()){
            int x=q.top().second;q.pop();
            if(vis[x])continue;
            vis[x]=1;
            for(int i=head[x];i;i=nxt[i]){
                int y=ver[i];
                if(d[y]>d[x]+edge[i]){
                    d[y]=d[x]+edge[i];
                    q.push(make_pair(-d[y],y));
                }
            }
        }
    }
    bool init(){
        for(int i=1;i<=n;i++)add(0,i,0);
        if(!spfa(0))return 0;
        for(int x=1;x<=n;x++){
            for(int i=head[x];i;i=nxt[i])
                edge[i]+=h[x]-h[ver[i]];
        }
        return 1;
    }
}js;