两种SPFA的模板(有快乐STL)

两种SPFA的模板(有快乐STL)

2019年11月5日 4 作者 Ender

抽时间学了下这个算法,但是NOI2018D1T1的故事告诉我们这个算法考场上不能用,这里提供一种手写邻接表,和一种vector邻接表的写法。

手写邻接表(加边纯属迷惑行为

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cstdio>
const long long inf = 2147483647;
const int M = 5e5 + 233;
const int N = 1e5 + 233;
struct edge {
    int v, w, next;
}e[M];
int h[M], etot, dist[N], m, n;
bool qJudge[N];
std::queue<int> q;

inline int read() {
    int x = 0, k = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-')k = -1;
        c = getchar();
    }
    while (c >= '0' &amp;&amp; c <= '9')x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    return x * k;
}
//inline void addEdge(int u, int v, int w) {
//    e[etot] = (edge){v, w, h[u]};
//    h[u] = etot++;
//}
inline void addEdge(int u, int v, int w) {
    e[++etot].next = h[u];
    e[etot].v = v;
    e[etot].w = w;
    h[u] = etot++;
}

inline void spfa(int origin) {
    for(int i=1; i<=n; i++) dist[i] = inf;
    dist[origin] = 0;
    qJudge[origin] = true;
    q.push(origin);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        qJudge[u] = false;
        for (int i = h[u]; i; i = e[i].next) {
            int v = e[i].v;
            if (dist[v] > dist[u] + e[i].w) {
                dist[v] = dist[u] + e[i].w;
                if (!qJudge[v]) {
                    q.push(v);
                    qJudge[v] = true;
                }
            }
        }
    }
}


int main() {
    int s;
    std::cin >> n >> m >> s;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        u = read();
        v = read();
        w = read();
        addEdge(u, v, w);
    }
    spfa(s);
    for (int i = 1; i <= n; i++)
        if (s == i) std::cout << 0 << " ";
        else std::cout << dist[i] << " ";
    return 0;
}

C++11并用vector存邻接表的写法

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cstdio>
const long long inf=2147483647;
const int M = 5e5 + 233;
const int N = 1e4 + 233;
struct edge {
    int v, w;
};
int h[N], etot, dist[N], m, n;
bool qJudge[N];
std::queue<int> q;

inline int read() {
    int x = 0, k = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-')k = -1;
        c = getchar();
    }
    while (c >= '0' &amp;&amp; c <= '9')x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    return x * k;
}
//inline void addEdge(int u, int v, int w) {
//    e[etot] = (edge){v, w, h[u]};
//    h[u] = etot++;
//}
std::vector<edge> e[N]; 
inline void spfa(int origin) {
    for(int i=1; i<=n; i++) dist[i] = inf;
    dist[origin] = 0;
    qJudge[origin] = true;
    q.push(origin);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        qJudge[u] = false;
        for (auto x : e[u]) {
            int v = x.v;
            int w = x.w;
			if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (!qJudge[v]) {
                    q.push(v);
                    qJudge[v] = true;
                }
            }
        }
    }
}


int main() {
    int s;
    std::cin >> n >> m >> s;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        u = read();
        v = read();
        w = read();
        e[u].push_back((edge){v,w});
//        addEdge(u, v, w);
    }
    spfa(s);
    for (int i = 1; i <= n; i++)
        if (s == i) std::cout << 0 << " ";
        else std::cout << dist[i] << " ";
    return 0;
}