bellman_ford.cpp

struct Edge {
  int from, to, cost;
  Edge(int from, int to, int cost) : from(from), to(to), cost(cost) {}
};

vector<optional<int>> BellmanFord(vector<Edge> &edges, int src, int node_size) {
  vector<optional<int>> dists(node_size);
  dists[src] = 0;
  for (int i = 0; i < node_size; ++i) {
    for (auto &e : edges) {
      if (!dists[e.from].has_value()) {
        continue;
      }

      int dist = dists[e.from].value() + e.cost;
      if (!dists[e.to].has_value() || dists[e.to].value() > dist) {
        dists[e.to] = dist;
        if (i == node_size - 1) {
          break;
        }
      }
    }
  }

  return dists;
}

bellman_ford_main.cpp

int main(int argc, const char *argv[]) {
  int n, m, s, g;
  cin >> n >> m >> s >> g;
  vector<Edge> edges;
  for (int i = 0; i < m; ++i) {
    int from, to, cost;
    cin >> from >> to >> cost;
    edges.emplace_back(from, to, cost);
  }

  auto dists = BellmanFord(edges, s, n);
  if (dists[g].has_value()) {
    cout << dists[g].value() << '\n';
  } else {
    cout << "Unreachable" << '\n';
  }
}

bellman_ford_test.txt

6 8 0 5
0 1 2
0 3 4
1 2 3
2 3 -2
2 5 2
3 4 2
3 5 4
4 5 1
// should out 6