kkogoro

最短路模板
最短路Dijkstra直接上堆优化了,我一般用用set+pair实现,如果有附带信息就struct+重载运算符然后...
扫描右侧二维码阅读全文
08
2018/11

最短路模板

最短路

Dijkstra

直接上堆优化了,我一般用用set+pair实现,如果有附带信息就struct+重载运算符然后set,注意重载小于号,如果对效率还有追求的话就用构造堆函数+大一点的数组来做

无法处理负边权,负边会破坏贪心

代码

洛谷P4779

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>



inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') {
            f = -1;
        }
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}


const int MAXN = 100007;
const int MAXM = 200007;


int to[MAXM], nextEdge[MAXM], w[MAXM], head[MAXN], cntEdge;
inline void addEdge(int u, int v, int W) {
    ++cntEdge;
    to[cntEdge] = v, w[cntEdge] = W, nextEdge[cntEdge] = head[u], head[u] = cntEdge;
    return;
}


const int INF = 0x3f3f3f3f;
typedef std::pair<int, int> PII;
typedef std::set<PII, std::less<PII> >::iterator Iter;
std::set<PII, std::less<PII> > min_heap;
int dis[MAXN];
bool vis[MAXN];
inline void Dijkstra(int s) {
    min_heap.clear();
    memset(dis, 0x3f, sizeof dis);
    memset(vis, 0, sizeof vis);
    dis[s] = 0;
    min_heap.insert(PII(dis[s], s));
    while (min_heap.size() > 0) {
        Iter top = min_heap.begin();
        int u = top->second;
        min_heap.erase(top);
        if (vis[u] == true) continue;

        vis[u] = true;
        for(int it = head[u]; it != 0; it = nextEdge[it]) {
            int v = to[it];
            if (vis[v] == false && dis[v] > dis[u] + w[it]) {
                dis[v] = dis[u] + w[it];
                min_heap.insert(PII(dis[v], v));
            }
        }
    }
    return;
}


int main() {
    int n = read();
    int m = read();
    int start = read();
    for (int i = 1; i <= m; ++i) {
        int u = read();
        int v = read();
        int W = read();
        addEdge(u, v, W);
    }
    Dijkstra(start);
    for (int i = 1; i <= n; ++i) {
        printf("%d ", dis[i] == INF ? 2147483647 : dis[i]);
    }
    return 0;
}

如果是struct+重载的话要注意这样写

struct Data {
    int u, dist;
    bool operator < (const Data &tmp) const {
        return dist < tmp.dist || (dist == tmp.dist && u < tmp.u);
    }
    Data(int dist, int u) : u(u), dist(dist) {}
};
std::set<Data> min_heap;

一定要吧比较的情况写全否则根据set判断相等的原则:不大于,不小于即为相等,会把dist相等的两个元素判为相等,然后就gg了。

而使用优先队列就不用考虑这个了,因为底层是堆,但是要注意优先队列的用法

q.push();
q.pop();
q.top();
q.size();
q.empty();
q.swap();
struct Data {
    int u, dist;
    bool operator < (const Data &tmp) const {
        return dist > tmp.dist;
    }
    Data(int dist, int u) : u(u), dist(dist) {}
};
std::priority_queue<Data> min_heap;

Floyd

经典的动态规划,同时需要掌握传递闭包问题,可以处理负边权但是无法处理负环

#include <iostream>
#include <cstdio>


inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') {
            f = -1;
        }
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}


const int MAXN = 1007;
const int INF = 0x3f3f3f3f;


int dis[MAXN][MAXN];
inline void init(int n) {
    for (int i = 1; i <= n; ++i) {
        dis[i][i] = 0;
        for (int j = i + 1; j <= n; ++j) {
            dis[i][j] = dis[j][i] = INF;
        }
    }
    return;
}
inline void Floyd(int n) {
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            if (dis[i][k] == INF) continue;
            for (int j = 1; j <= n; ++j) {
                if (dis[k][j] == INF) continue;
                dis[i][j] = std::min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
    return;
}


int main() {
    int n = read();
    int m = read();
    int start = read();
    init(n);
    for (int i = 1; i <= m; ++i) {
        int u = read();
        int v = read();
        int W = read();
        if (W < dis[u][v]) {
            dis[u][v] = W;
        }
    }
    Floyd(n);
    for (int i = 1; i <= n; ++i) {
        printf("%d ", dis[start][i] == INF ? 2147483647 : dis[start][i]);
    }
    return 0;
}

SPFA

Bellman Ford算法就不写了

死了的算法,如果保证边权非负就不要用了。

判断负环和正环的时候要用

const int INF = 0x3f3f3f3f;
int dis[MAXN];
bool inq[MAXN];
struct Queue {
    static const int maxn = 1 << 17;
    static const int mod = maxn - 1;
    int data[maxn], head, tail;
    inline void init() {
        head = 1, tail = 0;
        return;
    }
    inline void push(int x) {
        data[++tail & mod] = x;
        return;
    }
    inline void pop() {
        ++head;
        return;
    }
    inline int front() {
        return data[head & mod];
    }
    inline bool empty() {
        return head > tail;
    }
} q;
inline void SPFA(int start) {
    memset(inq, 0, sizeof inq);
    memset(dis, 0x3f, sizeof dis);
    q.init();
    dis[start] = 0;
    q.push(start);
    inq[start] = true;
    while (q.empty() == false) {
        int u = q.front();
        inq[u] = false;
        q.pop();
        for (int it = head[u]; it != 0; it = nextEdge[it]) {
            int v = to[it];
            if (dis[v] > dis[u] + w[it]) {
                dis[v] = dis[u] + w[it];
                if (inq[v] == false) {
                    inq[v] = true;
                    q.push(v);
                }
            }
        }
    }
    return;
}
Last modification:November 9th, 2018 at 11:15 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment