Bellman-Ford

bellman.cpp

// Rafał Hirsz
// 247955
// KLO

#include <cstdio>
#include <limits>
#include <vector>

struct Edge {
    int from, to;
    int weight;

    Edge(int from, int to, int weight): from(from), to(to), weight(weight) {}
};

template <typename T>
class Infinite {
public:
    T value;
    bool infinity;

    Infinite(): value(0), infinity(true) {}
    Infinite(T value): value(value), infinity(false) {}

    int operator()() { return infinity ? std::numeric_limits<T>::max() : value; }

    Infinite<T>& operator=(T other) {
        value = other;
        infinity = false;
        return *this;
    }
    Infinite<T>& operator=(const Infinite<T>& other) {
        value = other.value;
        infinity = other.infinity;
        return *this;
    }

    Infinite<T> operator+(T other) {
        return infinity ? Infinite<T>() : Infinite<T>(value + other);
    }
    Infinite<T> operator+(const Infinite<T>& other) {
        if (infinity || other.infinity) return Infinite<T>();
        return Infinite<T>(value + other.value);
    }
    Infinite<T> operator+(const Infinite<T>&& other) {
        if (infinity || other.infinity) return Infinite<T>();
        return Infinite<T>(value + other.value);
    }
    Infinite<T> operator-(T other) {
        return infinity ? Infinite<T>() : Infinite<T>(value - other);
    }
    Infinite<T> operator-(const Infinite<T>& other) {
        if (infinity || other.infinity) return Infinite<T>();
        return Infinite<T>(value - other.value);
    }
    Infinite<T> operator-(const Infinite<T>&& other) {
        if (infinity || other.infinity) return Infinite<T>();
        return Infinite<T>(value - other.value);
    }

    bool operator<(T other) {
        return infinity ? false : (value < other);
    }
    bool operator<(const Infinite<T>& other) {
        if (infinity) return false;
        if (other.infinity) return true;
        return value < other.value;
    }
    bool operator>(T other) {
        return infinity ? true : (value > other);
    }
    bool operator>(const Infinite<T>& other) {
        if (infinity && !other.infinity) return true;
        if (other.infinity) return false;
        return value > other.value;
    }
};

typedef std::vector<Edge> Edges;

int main() {
    int n, m, root;
    scanf("%d %d %d\n", &n, &m, &root);

    std::vector<Infinite<int> > vertices;
    Edges edges;

    int a, b, c, i;
    for (i=0; i<m; i++) {
        scanf("%d %d %d", &a, &b, &c);
        edges.push_back( Edge(a, b, c) );
    }

    // Initialize
    for (i=0; i<n; i++) {
        vertices.push_back( Infinite<int>() );
    }

    vertices[root] = 0;

    // Perform the Bellman-Ford algorithm
    for (i=0; i<n; i++) {
        for (Edges::iterator it = edges.begin(); it != edges.end(); it++) {
            if (vertices[it->from] + it->weight < vertices[it->to]) {
                vertices[it->to] = vertices[it->from] + it->weight;
            }
        }
    }

    // Detect negative cycles
    for (Edges::iterator it = edges.begin(); it != edges.end(); it++) {
        if (vertices[it->from] + it->weight < vertices[it->to] ) {
            printf("NIE\n");
            return 0;
        }
    }

    // Print out
    for (i=0; i<n; i++) {
        if (i == root) continue;
        if (vertices[i].infinity) continue;

        printf("%d %d\n", i, vertices[i]());
    }

    return 0;
}