ベルマンフォードアルゴリズムを用いた方向図の最小距離コスト

方向図では、1つの頂点から別の頂点への最小コストのコードです。

#include <iostream>
#include <vector>

using namespace std;

struct Data {
    int s, e, val;
    Data(int a, int b, int c) {
        s = a;
        e = b;
        val = c;
    }
};

int n, m, answer_s, answer_e;
int dist[101];
vector<Data> graph;

int main() {
    freopen("input.txt", "rt", stdin);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph.push_back(Data(a, b, c));
    }
    for (int i = 1; i <= n; i++) {
        dist[i] = 2147000000;       // 무한대로 초기화
    }
    cin >> answer_s >> answer_e;
    dist[answer_s] = 0;     // 출발 정점
    for (int i = 1; i < n; i++) { // 간선 i개로 가는 경우를 말한다.
        for (int j = 0; j < graph.size(); j++) {
            int s = graph[j].s;
            int e = graph[j].e;
            int val = graph[j].val;
            if (dist[s] != 2147000000 && dist[s] + val < dist[e]) {
                dist[e] = dist[s] + val;
            }
        }
    }
    for (int j = 0; j < graph.size(); j++) {
        int s = graph[j].s;
        int e = graph[j].e;
        int val = graph[j].val;
        if (dist[s] != 2147000000 && dist[s] + val < dist[e]) {
            cout << "-1\n";
            return 0;
        }
    }
    cout << dist[answer_e];
    return 0;
}

for (int i=1; i<n; i++) { for(int j=0; j<graph.size(); j++)}:変数iに対応するfor loopは、始点から幹線iまでの到達可能な頂点を記録する.

すなわち,1本の幹線からn−1本の幹線を用いた場合,すべての数を記録する.

ベルマンフォードアルゴリズムの特徴