벨만포드 C++ 코드

#include <iostream>
#include <vector>
#include <tuple>

using namespace std;

const int INF = 1e9;

bool bellmanFord(int start, int n, vector<tuple<int, int, int>>& edges, vector<int>& dist) {
    dist[start] = 0;

    // 모든 간선을 최대 (V-1)번 반복
    for (int i = 0; i < n - 1; i++) {
        for (auto& edge : edges) {
            int u, v, weight;
            tie(u, v, weight) = edge;

            if (dist[u] != INF && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
            }
        }
    }

    // 음수 사이클 체크
    for (auto& edge : edges) {
        int u, v, weight;
        tie(u, v, weight) = edge;

        if (dist[u] != INF && dist[u] + weight < dist[v]) {
            return false; // 음수 사이클이 존재
        }
    }

    return true; // 음수 사이클이 없음
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<tuple<int, int, int>> edges;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edges.push_back({u, v, w});
    }

    int start;
    cin >> start;

    vector<int> dist(n, INF);
    bool noNegativeCycle = bellmanFord(start, n, edges, dist);

    if (noNegativeCycle) {
        for (int i = 0; i < n; i++) {
            if (dist[i] == INF) {
                cout << "Node " << i << ": Unreachable" << endl;
            } else {
                cout << "Node " << i << ": " << dist[i] << endl;
            }
        }
    } else {
        cout << "Negative cycle detected in the graph." << endl;
    }

    return 0;
}