Wormholes solution

wormholes.cpp

// Wormholes <http://nztrain.com/problems/98>

#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

// This can't be INT_MAX -- adding anything to INT_MAX would cause it to
// overflow and become negative.
// Kudos to Alan Ansell for pointing that out
const int VERY_BIG_NUMBER = 1001;

struct edge {
    size_t from, to;
    int cost;
    };

void bellman_ford(vector<int> &distances, size_t n_nodes, const vector<edge> &edges, size_t source) {
    for (size_t i = 0; i != n_nodes; ++i) {
        if (i == source)
            distances.push_back(0);
        else
            distances.push_back(VERY_BIG_NUMBER);
        }

    for (size_t i = 0; i != distances.size()-1; ++i) {
        for (size_t j = 0; j != edges.size(); ++j) {
            const edge &e = edges[j];
            distances[e.to] = min(distances[e.from]+e.cost, distances[e.to]);
            //fprintf(stderr, "Distance from %zu to %zu is now %d\n", e.from, e.to, distances[e.to]);
            }
        }
    }

int main() {
    freopen("worm.in", "r", stdin);
    freopen("worm.out", "w", stdout);

    size_t n_cases;
    scanf("%zu", &n_cases);

    for (size_t c = 0; c != n_cases; ++c) {
        vector<int> distances;
        vector<edge> edges;

        size_t n_nodes, n_edges;
        scanf("%zu %zu", &n_nodes, &n_edges);

        for (size_t i = 0; i != n_edges; ++i) {
            edge e;
            scanf("%zu %zu %d", &e.from, &e.to, &e.cost);
            edges.push_back(e);
            }

        bellman_ford(distances, n_nodes, edges, 0);

        bool has_cycle = false;
        for (size_t i = 0; i != edges.size(); ++i) {
            const edge &e = edges[i];
            if (distances[e.from]+e.cost < distances[e.to]) {
                has_cycle = true;
                break;
                }
            }

        puts(has_cycle ? "possible" : "not possible");
        }

    return 0;
    }