BellmanFord

1
auto res = bellmanford(g, s, e);

1
struct bellmanford_return {
2
  vector<int> path, distances;
3
  bool hascycle;
4
};
5
bellmanford_return bellmanford(DirectedGraph &_g,int s, int e) {
6
  vector<int> cnt(_g.g.size()), dist(_g.g.size(), INF), path, p(_g.g.size(), -1);
7
  vector<bool> inque(_g.g.size());
8
  queue<int> q;
9
  dist[s] = 0;
10
  q.push(s);
11
  inque[s] = true;
12
  while (!q.empty()) {
13
    const int from = q.front();
14
    q.pop();
15
    inque[from] = false;
16
    for (const auto &edge : g[from]) {
17
      const int d = (dist[from] + edge.cost);
18
      if (d < dist[edge.to]) {
19
        dist[edge.to] = d;
20
        p[edge.to] = from;
21
        if (!inque[edge.to]) {
22
          q.push(edge.to);
23
          inque[edge.to] = true;
24
          ++cnt[edge.to];
25
          if ((int)g.size() < cnt[edge.to])
26
            return {vector<int>(), vector<int>(), true};
27
        }
28
      }
29
    }
30
  }
31
  if (dist[e] != INF) {
32
    for (int i = e; i != -1; i = p[i])
33
      path.push_back(i);
34
    reverse(path.begin(), path.end());
35
  }
36
  return {path, dist, false};
37
}