ベルマンフォード法

最短経路問題

問題　:　動作確認済み

(条件)
N 頂点と M 辺からなる有向グラフ
頂点 1 から N を目指す

(ポイント)
(無向グラフなら)永遠に値を小さくできる

未到達の点も含めて1ループごとにすべての辺を更新する

頂点数ループすると一周する

using ll = long long;
const ll INF = 1LL << 50;    

int main(void) {
    int N, M;
    cin >> N >> M;
    const int NMAX = 1000; //制約
    const int MMAX = 2000;
    int a[MMAX], b[MMAX]; //頂点 a[i] → b[i]
    ll c[MMAX]; //重み

    for (int i = 0; i < M; ++i) {
        cin >> a[i] >> b[i] >> c[i];
        //c[i] = -c[i]; //最大値を求める場合
    }

    ll dist[NMAX];

    for (int i = 0; i < N; ++i)  dist[i] = INF;
 
    dist[0] = 0;

    //1ループごとにすべての辺を更新する。
    for (int loop = 0; loop < N - 1; ++ loop) {
        for (int i = 0; i < M; ++i) {
             if (dist[a[i] - 1] == INF) continue; 

             if (dist[b[i] - 1] > dist[a[i] - 1] + c[i]) { 
             dist[b[i] - 1] = dist[a[i] - 1] + c[i];
             }
         }
     }
    ll ans = dist[N - 1]; // 最短経路


    bool negative[NMAX]; // 負の経路判定

    for (int i = 0; i < N; ++i) {
        negative[i] = false;
    }
    //もう1周loopさせ、同じ点を通れば負のループが存在する。
    for (int loop = 0; loop < N ; ++ loop) {
        for (int i = 0; i < M; ++i) {
            if (dist[a[i] - 1] == INF) continue;

            if (dist[b[i] - 1] > dist[a[i] - 1] + c[i]) {
                dist[b[i] - 1] = dist[a[i] - 1] + c[i];
                negative[b[i] - 1] = true;
            }
    
            if (negative[a[i] - 1] == true) {
                negative[b[i] - 1] = true;
            }
        }
    }


     if (negative[N - 1])//負の経路なら
         cout << "inf" << endl;
     else
         cout << -ans << endl;

     return 0;
 }