最短路ex

Tony43 · 2019-08-18 17:36:56 · 个人记录

最短路计数

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
inline void read(int& x) {
    char c=getchar();
    while(c<'0') c=getchar();
    for(x=0;c>='0';c=getchar()) x=(x<<3)+(x<<1)+(c^48);
}
int n,m,d[100010];
struct p {
    int to,dis;
    bool operator < (const p &t) const {
        return dis>t.dis;
    }
};
int head[100010],ver[200010],cost[200010],nt[200010],z=0;
inline void addedge(int a,int b,int c) {
    nt[++z]=head[a],head[a]=z,ver[z]=b,cost[z]=c;
}
priority_queue<p> q;
short vis[100010];
long long cnt[100010];// s到i的最短路条数
inline void work(int s) {
    memset(d,0x3f,sizeof(d));
    d[s]=0,q.push(p {s,0}),cnt[s]=1;
    while(!q.empty()) {
        int x=q.top().to;
        q.pop();
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=head[x]; i; i=nt[i]) {
            int y=ver[i];
            if(d[y]==d[x]+cost[i]) cnt[y]+=cnt[x];
            else if(d[y]>d[x]+cost[i]) {
                d[y]=d[x]+cost[i];
                cnt[y]=cnt[x];
                q.push(p {y,d[y]});
            }
        }
    }
}
int main() {
    scanf("%d%d",&n,&m);
    int u,v,w;
    for(int i=1; i<=m; i++) {
        scanf("%d%d%d",&u,&v,&w);
        addedge(u,v,w);
    }
    work(1);
    if(cnt[n]) printf("%d %lld",d[n],cnt[n]);
    else printf("Can't arrive");
    return 0;
}

次短路

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
int n,m,d[100010],d2[100010];//1，n的单源最短路
int fr[200010],to[200010],ct[200010];//存下边
struct p {
    int to,dis;
    bool operator < (const p &t) const {
        return dis>t.dis;
    }
};
int head[100010],ver[200010],cost[200010],nt[200010],z=0;
inline void addedge(int a,int b,int c) {
    nt[++z]=head[a],head[a]=z,ver[z]=b,cost[z]=c;
}
int head2[100010],ver2[200010],cost2[200010],nt2[200010],z2=0;
inline void addedge2(int a,int b,int c) {
    nt2[++z2]=head2[a],head2[a]=z2,ver2[z2]=b,cost2[z2]=c;
}
priority_queue<p> q;
short vis[100010];
inline void work(int s) {
    memset(d,0x3f,sizeof(d));
    d[s]=0,q.push(p {s,0});
    while(!q.empty()) {
        int x=q.top().to;
        q.pop();
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=head[x]; i; i=nt[i]) {
            int y=ver[i];
            if(d[y]>d[x]+cost[i]) {
                d[y]=d[x]+cost[i];
                q.push(p {y,d[y]});
            }
        }
    }
}
inline void work2(int s) {
    memset(d2,0x3f,sizeof(d2));
    d2[s]=0,q.push(p {s,0});
    while(!q.empty()) {
        int x=q.top().to;
        q.pop();
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=head2[x]; i; i=nt2[i]) {
            int y=ver2[i];
            if(d2[y]>d2[x]+cost2[i]) {
                d2[y]=d2[x]+cost2[i];
                q.push(p {y,d2[y]});
            }
        }
    }
}
int main() {
    // 次短路
    // 显然，如果严格次短路存在，那么它一定是这种形式：(d[i][j]表示i到j的最短路)
    // d[s][x]+e(x,y)+d[y][t]
    // 所以双向最短路+枚举边即可
    scanf("%d%d",&n,&m);
    int u,v,w;
    for(int i=1; i<=m; i++) {
        scanf("%d%d%d",&u,&v,&w);
        addedge(u,v,w);
        addedge2(v,u,w);
        fr[i]=u,to[i]=v,ct[i]=w;
    }
    work(1);
    memset(vis,0,sizeof(vis));
    work2(n);
    int dis=d[n],ans=0x3f3f3f3f;
    for(int i=1; i<=m; i++) {
        int ddis=d[fr[i]]+ct[i]+d2[to[i]];
        if(ddis>dis) {
            if(ddis<ans) ans=ddis;
        }
    }
    printf("%d",ans);
    return 0;
}

最长路

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
int n,m;
int head[100010],ver[200010],cost[200010],nt[200010],z=0;
inline void addedge(int a,int b,int c) {
    nt[++z]=head[a],head[a]=z,ver[z]=b,cost[z]=c;
}
int d[100010];
short inq[100010];
int c[100010];
queue<int> q;
inline int work(int s) {
    memset(d,0x3f,sizeof(d));
    q.push(s),d[s]=0,inq[s]=1,c[s]=1;
    while(!q.empty()) {
        int x=q.front();
        q.pop(),inq[x]=0;
        for(int i=head[x]; i; i=nt[i]) {
            int y=ver[i];
            if(d[y]>d[x]+cost[i]) {
                d[y]=d[x]+cost[i];
                if(inq[y]) continue;
                if(++c[y]>=n) return 1;
                q.push(y),inq[y]=1;
            }
        }
    }
    return 0;
}
int main() {
    //最长路 
    //边权取相反数后跑spfa即可  判负环->判正环
    scanf("%d%d",&n,&m);
    int u,v,w;
    for(int i=1; i<=m; i++) {
        scanf("%d%d%d",&u,&v,&w);
        addedge(u,v,-w);
    }
    if(work(1)) printf("any value");
    else {
        if(d[n]==0x3f3f3f3f) printf("can't arrive");
        else printf("%d",-d[n]);
    }
    return 0;
}

判负环

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <stack>
using namespace std;
int n,m;
int head[100010],ver[200010],cost[200010],nt[200010],z=0;
inline void addedge(int a,int b,int c) {
    nt[++z]=head[a],head[a]=z,ver[z]=b,cost[z]=c;
}
int d[100010];
short inq[100010];
int cnt[100010],sum[100010];
queue<int> q;
inline bool work(int s) {
    memset(d,0x3f,sizeof(d));
    d[s]=0,q.push(s),inq[s]=1,sum[s]=1;
    while(!q.empty()) {
        int x=q.front();
        q.pop(),inq[x]=0;
        for(int i=head[x]; i; i=nt[i]) {
            int y=ver[i];
            if(d[y]>d[x]+cost[i]) {
                d[y]=d[x]+cost[i];
                cnt[y]=cnt[x]+1;
                if(cnt[y]>=n) return true;
                if(!inq[y]) {
                    if(++sum[y]>=n) return true;
                    q.push(y),inq[y]=1;
                }
            }
        }
    }
    return false;
}
int main() {
    scanf("%d%d",&n,&m);
    int u,v,w;
    for(int i=1; i<=m; i++) {
        scanf("%d%d%d",&u,&v,&w);
        addedge(u,v,w);
    }
    if(work(1)) printf("Yes\n");
    else printf("No\n");
    return 0;
}