src/BellmanFord.hpp

View this file on GitHub
Last update: 2021-02-22 09:25:55+09:00
Include: #include "src/BellmanFord.hpp"

Depends on

Verified with

test/aoj/GRL_1_B.test.cpp

Code

#pragma once

#include <vector>
#include <algorithm>

#include "chmin.hpp"
#include "Edge.hpp"

using namespace std;

template<class T>
vector<T> BellmanFord(const vector<Edge<T>> &edges, const int V, const int st) {

    const T inf = numeric_limits<T>::max() / 2;
    vector<T> cost(V, inf);
    cost[st] = 0;
    for (int i = 0; i < V - 1; i++) {
        for (const auto &e : edges) {
            if (cost[e.from] == inf) continue;
            chmin(cost[e.to], cost[e.from] + e.cost);
        }
    }

    for (int i = 0; i < V; i++) {
        for (const auto &e : edges) { // finding negative loop
            if (cost[e.from] == inf) continue;
            if (cost[e.from] == -inf) cost[e.to] = -inf; // src is nloop -> dst is nloop
            else if (cost[e.to] > cost[e.from] + e.cost) cost[e.to] = -inf; // chmin is possible -> nloop
        }
    }

    return cost;
}

#line 2 "src/BellmanFord.hpp"

#include <vector>
#include <algorithm>

#line 2 "src/chmin.hpp"

template<class T>
inline bool chmin(T &a, const T b) { return a > b && (a = b, true); }
#line 2 "src/Edge.hpp"

template<class T>
struct Edge {
    int from{}, to{};
    T cost;
    Edge() = default;
    Edge(int to, T cost) : to(to), cost(move(cost)) {}
    Edge(int from, int to, T cost) : from(from), to(to), cost(move(cost)) {}
    bool operator>(const Edge &r) const { return this->cost > r.cost; }
};
#line 8 "src/BellmanFord.hpp"

using namespace std;

template<class T>
vector<T> BellmanFord(const vector<Edge<T>> &edges, const int V, const int st) {

    const T inf = numeric_limits<T>::max() / 2;
    vector<T> cost(V, inf);
    cost[st] = 0;
    for (int i = 0; i < V - 1; i++) {
        for (const auto &e : edges) {
            if (cost[e.from] == inf) continue;
            chmin(cost[e.to], cost[e.from] + e.cost);
        }
    }

    for (int i = 0; i < V; i++) {
        for (const auto &e : edges) { // finding negative loop
            if (cost[e.from] == inf) continue;
            if (cost[e.from] == -inf) cost[e.to] = -inf; // src is nloop -> dst is nloop
            else if (cost[e.to] > cost[e.from] + e.cost) cost[e.to] = -inf; // chmin is possible -> nloop
        }
    }

    return cost;
}