Submission #1531580

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <functional>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <vector>
#include <array>
#include <tuple>
#include <utility>
#include <numeric>
#include <iomanip>
#include <cctype>
#include <cmath>
#include <assert.h>
#include <cstdlib>
#include <list>
using namespace std;

using ll = long long;
using ull = unsigned long long;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;

template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {
    return s << "(" << p.first << ", " << p.second << ")";
}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
    s << "[";
    for (int i = 0; i < v.size(); i++) s << (i == 0 ? "" : ", ") << v[i];
    s << "]";
    return s;
}

#define ALL(a) (a).begin(), (a).end()

using Weight = ll;

// 重み付きの辺
struct Edge {
    int from, to;
    Weight weight;

    Edge() {}
    Edge(int to) : from(-1), to(to), weight(-1) {}
    Edge(int from, int to) : from(from), to(to), weight(-1) {}
    Edge(int from, int to, Weight weight) : from(from), to(to), weight(weight) {}

    bool operator<(const Edge& e) const {
        return (weight != e.weight) ? (weight < e.weight) : (from < e.from);
    }
    bool operator>(const Edge& e) const {
        return (weight != e.weight) ? (weight > e.weight) : (from > e.from);
    }
};

using Arc = Edge;
using Graph = vector<vector<Edge>>;
using DGraph = vector<vector<Arc>>;

using Tree = Graph;

// 最初に初期化することを忘れないように!
using GArray = vector<Weight>;
using GMatrix = vector<GArray>;

// この4つの関数は頂点数を固定したバージョンでも動く
void add_edge(Graph& g, int u, int v, Weight w = -1) {
    g[u].push_back(Edge(u, v, w));
    g[v].push_back(Edge(v, u, w));
}

void add_arc(DGraph& dg, int u, int v, Weight w = -1) {
    dg[u].push_back(Arc(u, v, w));
}

namespace BellmanFord {
    DGraph dgraph;
    int V;
    vector<Weight> cost;
    const Weight INF = (1LL << 50);

    void initialize(DGraph& dg) {
        V = dg.size();
        dgraph = dg;
        cost.resize(V);
    }

    // 負の閉路を見つけたらtrueを返す
    bool solve(int s) {
        for (int v = 0; v < V; v++) cost[v] = INF;
        cost[s] = 0;

        bool update = true;
        for (int i = 0; i <= V && update; i++) {
            update = false;

            for (int from = 0; from < V; from++) {
                for (Arc& a : dgraph[from]) {
                    if (cost[a.from] != INF && cost[a.to] > cost[a.from] + a.weight) {
                        cost[a.to] = cost[a.from] + a.weight;
                        update = true;
                    }
                }
            }
        }
        return update;
    }
};

int main() {
    int N, M;
    cin >> N >> M;

    DGraph dgraph(N);
    for (int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        add_arc(dgraph, a, b, -c);
    }

    BellmanFord::initialize(dgraph);
    if (BellmanFord::solve(0)) cout << "inf" << endl;
    else cout << -BellmanFord::cost[N - 1] << endl;

    return 0;
}

Submission Info

Judge Result