Submission #1673591

---

Source Code Expand

#include <algorithm>
#include <complex>
#include <iostream>
#include <vector>
#include <iomanip>
#include <queue>

#define REP(i, m, n) for(int i=int(m);i<int(n);i++)
#define EACH(i, c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s, e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

//#define LOCAL 0
//#ifdef LOCAL
//#define DEBUG(s) cout << (s) << endl
//#define dump(x)  cerr << #x << " = " << (x) << endl
//#define BR cout << endl;
//#else
//#define DEBUG(s) do{}while(0)
//#define dump(x) do{}while(0)
//#define BR
//#endif


//改造
typedef long long int ll;
using namespace std;
#define INF (1 << 20)
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね

//ここから編集する

/*
 * ベルマンフォード方法による最短路問題
 * 0ビギナーであることに注意
 *                                 */
struct edge {
    int from, to;
    ll cost;
};
vector<edge> es; // 辺
vector<ll> d; //最短距離,0で初期化してね
int V, E;//頂点数と辺の数

bool find_negative_loop(int s) {
    //dは0で初期化しておくyu7y
    d[s] = 0;
    for (int i = 0; i < V; i++) {

        for (int j = 0; j < E; j++) {
            edge e = es[j];
            if (d[e.from] == INFl) continue;
            if (d[e.to] > d[e.from] + e.cost) {
                d[e.to] = d[e.from] + e.cost;
                if (i == V - 1) return true;
            }
        }
    }
    return false;
}

/* negative check */
vector<bool> negative;

void negative_check() {
    negative = vector<bool>(V,false);
    for (int i = 0; i < V; i++) {

        for (int j = 0; j < E; j++) {
            edge e = es[j];
            if (d[e.from] == INFl) continue;
            if (d[e.to] > d[e.from] + e.cost) {
                d[e.to] = d[e.from] + e.cost;
                negative[e.to] = true;
//                if (i == V - 1) return true;
            }
        }
    }
//    return false;
}

void print_d() {
    if (DEBUG) {
        REP(i, 0, d.size()) {
            cout << d[i] << " ";
        }
        cout << endl;
    }
}

int main() {
    queue<int> que;
    int N, M;
    cin >> N >> M;
    V = N;
    E = M;
    d = vector<ll>(V, INFl);
//    d[0] = 0;
    es = vector<edge>(E);

    REP(i, 0, M) {
        edge e;
        cin >> e.from >> e.to >> e.cost;
        e.from--;
        e.to--;
        e.cost *= -1;
        es[i] = e;
    }
//    d[0] = 0;
    find_negative_loop(0);
    ll ans = -d[N-1];
    negative_check();

    if (negative[N-1]) {
        cout << "inf" << endl;
    } else {
//        cout << -d[N-1] << endl;
        cout << -d[N - 1] << endl;
    }
    print_d();
    return 0;
}

Submission Info

Judge Result