最短路算法模板SPFA、disjkstra、Floyd

朴素SPFA（链表建边）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define MAXN 1000008
#define INF  2147483647

using namespace std;

int first[MAXN], next[MAXN];
int u[MAXN], v[MAXN], w[MAXN];
int dis[MAXN];
bool vis[MAXN];
int n, m, s;
queue<int> P;

int main() {
    memset(first, -1, sizeof(first));
    scanf("%d%d%d", &n, &m, &s);
    for(int i=1; i<=n; i++) {
        dis[i] = INF;
    }
    dis[s] = 0;
    for(int i=1; i<=m; i++) {
        scanf("%d%d%d", &u[i], &v[i], &w[i]);
        next[i] = first[u[i]];
        first[u[i]] = i;
    }
    P.push(s), vis[s] = 1;
    while(!P.empty()) {
        int x = P.front();
        int k = first[x];
        P.pop();
        while(k != -1) {
            if(dis[v[k]] > dis[u[k]]+w[k]) {
                dis[v[k]] = dis[u[k]]+w[k];
                if(vis[v[k]] == 0) {
                    P.push(v[k]);
                    vis[v[k]] = 1;
                }
            }
            k = next[k];
        }
        vis[x] = 0;
    }
    for(int i=1; i<=n; i++) {
        printf("%d ", dis[i]);
    }
    return 0;
}

 

---

 

 

朴素dijkstra（链表建边）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define MAXN 500000
#define INF  2147483647

using namespace std;

int first[MAXN], next[MAXN];
int u[MAXN], v[MAXN], w[MAXN];
int dis[MAXN];
bool book[MAXN];
int n, m, s;

int main() {
    scanf("%d%d%d", &n, &m, &s);
    memset(first, -1, sizeof(first));
    for(int i=1; i<=n; i++) {
        dis[i] = INF;
    }
    dis[s] = 0;
    for(int i=1; i<=m; i++) {
        scanf("%d%d%d", &u[i], &v[i], &w[i]);
        next[i] = first[u[i]];
        first[u[i]] = i;
    }
    //book[s] = 1;
    for(int i=1; i<n; i++) {
        int minn = INF, x;
        for(int j=1; j<=n; j++) {
            if(dis[j] < minn&&book[j] == 0) {
                minn = dis[j];
                x = j;
            }
        }
        book[x] = 1;
        int k = first[x];
        while(k != -1) {
            if(dis[v[k]] > dis[u[k]]+w[k]) {
                dis[v[k]] = dis[u[k]]+w[k];
            }
            k = next[k];
        }
    }
    for(int i=1; i<=n; i++) {
        printf("%d ", dis[i]);
    }
}

 

---

 

 

Floyd（矩阵建边）

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#define INF 214748364

using namespace std;

int n, m, s, t;
int dis[1005][1005];

int main() {
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            dis[i][j] = (i == j)?0:INF;
        }
    }
    for(int i=1; i<=m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        dis[u][v] = w;
        dis[v][u] = w;
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(dis[i][j] > dis[i][k]+dis[k][j]) {
                    dis[i][j] = dis[i][k]+dis[k][j];
                }
            }
        }
    }
    scanf("%d%d", &s, &t);
    printf("%d", dis[s][t]);
}