Detecting Anomalies in Currency Exchange Rates

题目链接：pdf

题目给一个有向图，判定这个有向图是不是存在负环。

思路：

对这个图进行Bellman-Ford算法：不断对所有边进行松弛操作，循环进行V次，如果第V次仍然有边被松弛，那么说明存在负环。

相反，如果第V次没有边被松弛，那么说明没有负环。

在讨论Dijkstra算法的时候，最开始的V*E的算法其实就是Bellman-Ford算法。

初始化的时候把dist数组初始化为0。为什么呢？因为我们找的是负环，所以我们可以假设所有点到对源点的距离都是0。如果有负环，那么一定有负边，在第V次松弛所有边的时候，这个环中一定有一个点的最短路为负值。

// Mon May 15 14:13:09 CST 2017
// Mon May 15 15:09:41 CST 2017


// 一个有向图是不是存在负环

#include <iostream>
#include <vector>
#include <utility>

using namespace std;
typedef pair<int, int> PII;	// from, to
struct edge {
  int from;
  int to;
  int w;
};

int negative_cycle(vector<vector<int> > &adj, vector<vector<int> > &cost) {
  vector<int> dist(adj.size(), 0);
  vector<edge> edges;

  for (size_t i = 0; i < adj.size(); ++i) {
    for (size_t j = 0; j < adj[i].size(); ++j) {
      edge e;
      e.from = i;
      e.to = adj[i][j];
      e.w = cost[i][j];
      edges.push_back(e);
    }
  }

  for (size_t i = 0; i < adj.size(); ++i) {
    for (auto &e : edges) {
      int tmp = dist[e.from] + e.w;

      if (dist[e.to] > tmp) {
	dist[e.to] = tmp;
	if (i == adj.size() - 1) {
	  return 1;
	}
      }
    }
  }

  return 0;
}

int main() {
  int n, m;

  cin >> n >> m;
  
  // using this will fail on test19. I don't know why!
  // while(std::cin >> n >> m) {
    vector<vector<int> > adj(n, vector<int>());
    vector<vector<int> > cost(n, vector<int>());
    
    for (int i = 0; i < m; i++) {
      int x, y, w;
      std::cin >> x >> y >> w;
      adj[x - 1].push_back(y - 1);
      cost[x - 1].push_back(w);
    }
    std::cout << negative_cycle(adj, cost) << "\n";
  // }

  return 0;
}