POJ 3259 - Wormholes: Bellman-Form algorithm to detect negative cycles

wormhole.cc

#include <iostream>
#include <vector>

using namespace std;

// Given the info from the problem statement.
const int kInf = 10001;

struct Edge {
  int src_;
  int dest_;
  int time_cost_;
  Edge(int src, int dest, int time_cost) :
      src_(src), dest_(dest), time_cost_(time_cost) {}
};

// Bellman-Form algorithm.
bool HasNegativeCycle(const vector<Edge>& edges, int node_num) {
  vector<int> dist(node_num + 1, kInf);
  // Starting from node 1.
  dist[1] = 0;
  // A flag indicating stable distances.
  bool dist_stable = false;
  
  // Update distances for n times. 
  // Cannot have negative cycles if the distance is stable within n loops.
  for (int i = 0; i < node_num; ++i) {
    // A flag indicating modification happens.
    bool dist_modified = false;
    // Traverse the edges.
    for (int edge_idx = 0, len = edges.size(); edge_idx < len; ++edge_idx) {
      int src = edges[edge_idx].src_,
          dest = edges[edge_idx].dest_,
          time_cost = edges[edge_idx].time_cost_;
      int new_dist = dist[src] + time_cost;
      if (new_dist < dist[dest]) {
        dist_modified = true;
        dist[dest] = new_dist;
      }
    }
    if (!dist_modified) {
      // Distances now stable.
      dist_stable = true;
      break;
    }
  }

  return !dist_stable;
}

int main() {
  int farm_num;
  cin >> farm_num;

  while (farm_num--) {
    int node_num, edge_num, wormhole_num;
    cin >> node_num >> edge_num >> wormhole_num;
    vector<Edge> edges;
    edges.reserve(edge_num * 2 + wormhole_num);

    while (edge_num--) {
      int src, dest, time_cost;
      cin >> src >> dest >> time_cost;
      edges.push_back(Edge(src, dest, time_cost));
      edges.push_back(Edge(dest, src, time_cost));
    }
    while (wormhole_num--) {
      int src, dest, time_reversed;
      cin >> src >> dest >> time_reversed;
      edges.push_back(Edge(src, dest, -time_reversed));
    }

    bool has_negative_cycles = HasNegativeCycle(edges, node_num);
    cout << (has_negative_cycles ? "YES" : "NO") << endl;
  }
  return 0;
}