最短路常用三种算法

弱化版题目luogu3371
标准版题目luogu4779

单源

spfa(可以卡成bellmanford复杂度 不建议用 但是随机图快 负权图还是可以用)

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<ctime>
#include<queue>
#include<iostream>
#include<stack>
#include<vector>
#include<bitset>
#include<set>
#include<map>
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define clr(a,x) memset(a,x,sizeof(a))
#define inf (0x7fffffff)
typedef long long ll;
using namespace std;
int readint(){
    int ans = 0,f = 1;
    char c = getchar();
    while(!isdigit(c)){
        if(c == '-') f = -1;
        c = getchar();
    }
    while(isdigit(c)){
        ans = ans*10 + c - '0';
        c = getchar();
    }
    return f*ans;
}
char num_print[12];
void printint(int x){
    if(x == 0){
        putchar('0');
        return;
    }
    int tmp = x > 0 ? x : -x;
    if(x < 0) putchar('-');
    int cnt = 0;
    while(tmp > 0){
        num_print[cnt++] = tmp%10 + '0';
        tmp/=10;
    }
    while(cnt--) putchar(num_print[cnt]);
}
const int maxm = 2e5+9,maxn = 1e5+9; 
struct edge{
    int v,w;
    edge*next;
    edge(int V = 0,int W = 0):v(V),w(W){}
};
edge E[maxm],*pt = E,*fir[maxn];
void addedge(int u,int v,int w){
    pt->v = v;
    pt->w = w;
    pt->next = fir[u];
    fir[u] = pt++;
}
int n,m,s;
int d[maxn];
bool p[maxn];
void spfa(int N,int S){
    queue<int>Q;
    Q.push(S);
    for(int i = 1; i <= N; i ++)
        d[i] = 0x7fffffff;
    d[S] = 0;
    p[S] = 1;
    Q.push(S);
    while(!Q.empty()){
        int x = Q.front();
        Q.pop();
        p[x] = 0;
        for(edge*e = fir[x]; e != NULL; e = e->next){
            if(d[e->v] > d[x] + e->w){
                d[e->v] = d[x] + e->w;
                if(!p[e->v]){
                    p[e->v] = 1;
                    Q.push(e->v);
                }
            }
        }
    }
    for(int i = 1; i <= n; i ++){
        printf("%d",d[i]);
        putchar(i == n ? '\n' : ' ');
    }
}
int main(){
    //std::ios::sync_with_stdio(false);
    //freopen("#test.in","r",stdin);
    //freopen("#test.out","w",stdout);
    n = readint();m = readint();s = readint();
    while(m--){
        int u = readint(),v = readint(),w = readint();
        addedge(u,v,w);
    }
    spfa(n,s);
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

dijkstra(速度稳定 但是不能处理负权图 负权图需要结合johnson的方法)

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<ctime>
#include<queue>
#include<iostream>
#include<stack>
#include<vector>
#include<bitset>
#include<set>
#include<map>
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define clr(a,x) memset(a,x,sizeof(a))
#define inf (0x7fffffff)
typedef long long ll;
using namespace std;
int readint(){
    int ans = 0,f = 1;
    char c = getchar();
    while(!isdigit(c)){
        if(c == '-') f = -1;
        c = getchar();
    }
    while(isdigit(c)){
        ans = ans*10 + c - '0';
        c = getchar();
    }
    return f*ans;
}
char num_print[12];
void printint(int x){
    if(x == 0){
        putchar('0');
        return;
    }
    int tmp = x > 0 ? x : -x;
    if(x < 0) putchar('-');
    int cnt = 0;
    while(tmp > 0){
        num_print[cnt++] = tmp%10 + '0';
        tmp/=10;
    }
    while(cnt--) putchar(num_print[cnt]);
}
const int maxm = 5e5+9,maxn = 1e4+9; 
struct edge{
    int v,w;
    edge*next;
    edge(int V = 0,int W = 0):v(V),w(W){}
};
edge E[maxm],*pt = E,*fir[maxn];
void addedge(int u,int v,int w){
    pt->v = v;
    pt->w = w;
    pt->next = fir[u];
    fir[u] = pt++;
}
int n,m,s;
int d[maxn];
struct node{
    int x,d;
    node(int X = 0,int D = 0):x(X),d(D){}
    bool operator < (const node&A)const{
        return d > A.d;
    }
};
priority_queue<node>Q;
void dijkstra(int N,int S){
    Q.push(node(S,0));
    for(int i = 1; i <= N; i ++)
        d[i] = 0x7fffffff;
    d[S] = 0;
    while(!Q.empty()){
        node now = Q.top();
        Q.pop();
        if(now.d != d[now.x]) continue;
        for(edge*e = fir[now.x]; e != NULL; e = e->next){
            if(d[e->v] > d[now.x] + e->w){
                d[e->v] = d[now.x] + e->w;
                Q.push(node(e->v,d[e->v]));
            }
        }
    }
    for(int i = 1; i <= n; i ++){
        printf("%d",d[i]);
        putchar(i == n ? '\n' : ' ');
    }
}
int main(){
    //std::ios::sync_with_stdio(false);
    //freopen("#test.in","r",stdin);
    //freopen("#test.out","w",stdout);
    n = readint();m = readint();s = readint();
    while(m--){
        int u = readint(),v = readint(),w = readint();
        addedge(u,v,w);
    }
    dijkstra(n,s);
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

多源

floyd(用邻接矩阵 输入记得取min)

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<ctime>
#include<queue>
#include<iostream>
#include<stack>
#include<vector>
#include<bitset>
#include<set>
#include<map>
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define clr(a,x) memset(a,x,sizeof(a))
#define inf (0x7fffffff)
typedef long long ll;
using namespace std;
int readint(){
    int ans = 0,f = 1;
    char c = getchar();
    while(!isdigit(c)){
        if(c == '-') f = -1;
        c = getchar();
    }
    while(isdigit(c)){
        ans = ans*10 + c - '0';
        c = getchar();
    }
    return f*ans;
}
char num_print[12];
void printint(int x){
    if(x == 0){
        putchar('0');
        return;
    }
    int tmp = x > 0 ? x : -x;
    if(x < 0) putchar('-');
    int cnt = 0;
    while(tmp > 0){
        num_print[cnt++] = tmp%10 + '0';
        tmp/=10;
    }
    while(cnt--) putchar(num_print[cnt]);
}
const int maxn = 1009;
int d[maxn][maxn];
int n,m,s;
void floyd(int S){
    for(int k = 1; k <= n; k ++)
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= n; j ++)
                if(d[i][k] != inf && d[k][j] != inf)
                    d[i][j] = min(d[i][j],d[i][k] + d[k][j]);
    for(int i = 1; i <= n; i ++){
        printf("%d",d[S][i]);
        putchar(i == n ? '\n' : ' ');
    }
}
int main(){
    //std::ios::sync_with_stdio(false);
    //freopen("#test.in","r",stdin);
    //freopen("#test.out","w",stdout);
    n = readint();m = readint();s = readint();
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            if(i != j && !d[i][j])
                d[i][j] = inf;
    while(m--){
        int u = readint(),v = readint(),w = readint();
        if(u != v)
            d[u][v] = min(d[u][v],w);
    }
    floyd(s);
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

负权图Johnson

luogu5905
待补

Last modification:April 29th, 2020 at 11:32 pm
如果觉得我的文章对你有用,请随意赞赏