最短路算法模板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, -, sizeof(first));

    scanf("%d%d%d", &n, &m, &s);

    for(int i=; i<=n; i++) {

        dis[i] = INF;

    }

    dis[s] = ;

    for(int i=; 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] = ;

    while(!P.empty()) {

        int x = P.front();

        int k = first[x];

        P.pop();

        while(k != -) {

            if(dis[v[k]] > dis[u[k]]+w[k]) {

                dis[v[k]] = dis[u[k]]+w[k];

                if(vis[v[k]] == ) {

                    P.push(v[k]);

                    vis[v[k]] = ;

                }

            }

            k = next[k];

        }

        vis[x] = ;

    }

    for(int i=; i<=n; i++) {

        printf("%d ", dis[i]);

    }

    return ;

}

---

朴素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, -, sizeof(first));

    for(int i=; i<=n; i++) {

        dis[i] = INF;

    }

    dis[s] = ;

    for(int i=; 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=; i<n; i++) {

        int minn = INF, x;

        for(int j=; j<=n; j++) {

            if(dis[j] < minn&&book[j] == ) {

                minn = dis[j];

                x = j;

            }

        }

        book[x] = ;

        int k = first[x];

        while(k != -) {

            if(dis[v[k]] > dis[u[k]]+w[k]) {

                dis[v[k]] = dis[u[k]]+w[k];

            }

            k = next[k];

        }

    }

    for(int i=; 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[][];

int main() {

    scanf("%d%d", &n, &m);

    for(int i=; i<=n; i++) {

        for(int j=; j<=n; j++) {

            dis[i][j] = (i == j)?:INF;

        }

    }

    for(int i=; 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=; k<=n; k++) {

        for(int i=; i<=n; i++) {

            for(int j=; 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]);

}