Language: C++

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
template<typename T> using pq = priority_queue<T>;
template<typename T> using minpq = priority_queue<T, vector<T>, greater<T>>;
template<typename T, typename K> using ump = unordered_map<T, K>;
const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll e5 = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = n - 1; i >= 0; i--)
#define repone(i, n) for(ll i = 1; i <= (ll)(n); i++)
#define each(i, mp) for(auto& i:mp)
#define eb emplace_back
#define F first
#define S second
#define all(obj) (obj).begin(), (obj).end()

template<class T>
void dump_debug(T list) {
#ifdef MY_DEBUG
    each(e, list) cout << e << " ";
    printf("\n");
#endif
}

/* ------------- ANSWER ------------- */
/* ---------------------------------- */

struct edge {
    ll cost;
    ll to;

    edge(ll to, ll cost) : to(to), cost(cost) {};
};

struct edge2 {
    ll from;
    ll cost;
    ll to;

    edge2(ll from, ll to, ll cost) : from(from), to(to), cost(cost) {};
};

typedef vector<edge> ve;
typedef vector<ve> vve;

class DAG {
private:
    ll v, e;
    vve table;
    vl pre; // 最短路の直前の頂点
    vl d;
    vector<edge2> es;
    vector<bool> seen;
    vl scores;
public:
    // v: 頂点数
    // e: 辺の数
    DAG(ll v, ll e) : v(v), e(e) {
        table.resize(v);
        pre.resize(v, -1);
        d.resize(v, inf);
        es.resize(e);
        seen.resize(v);
        scores.resize(v);
    }

    void add(ll from, ll to, ll cost = 1) {
        table[from].eb(edge(to, cost));
        es.eb(edge2(from, to, cost));
    }

    vvl all_path() {
        vvl tmp = vector<vector<ll>>();
        vl tmp2 = vl();
        return _all_path(tmp, 0, tmp2);
    }

    vvl _all_path(vvl &ret, ll now, vl &path_now) {
        if (now == v - 1) {
            ret.eb(path_now);
        }
        each(e, table[now]) {
            if (!seen[e.to]) {
                path_now.eb(e.to);
                seen[e.to] = true;
                _all_path(ret, e.to, path_now);
                path_now.pop_back();
                seen[e.to] = false;
            }
        }
        return ret;
    }

    // O(e * logv)
    vl dijkstra(ll s) {
        for (ll i = 0; i < v; ++i) d[i] = inf;

        // pairを使っているのは、比較関数を利用するため
        priority_queue<P, vector<P>, greater<>> que;
        d[s] = 0;
        que.push(P(0, s));
        ll time = 0;

        while (!que.empty()) {
            P p = que.top();
            que.pop();
            ll min_v = p.S;
            if (d[min_v] < p.F) continue;

            each(ele, table[min_v]) {
                if (d[ele.to] > d[min_v] + ele.cost) {
                    d[ele.to] = d[min_v] + ele.cost;
                    que.push(P(d[ele.to], ele.to));
                }
            }
        }
        return move(d);
    }

    // 頂点tへの最短路
    vector<int> get_path(int t) {
        vector<int> path;
        for (; t != -1; t = pre[t]) path.emplace_back(t); // tがsになるまでpre[t]をたどっていく
        reverse(path.begin(), path.end());
        return move(path);
    }

    vl bellman_ford(int s) {
        for (int i = 0; i < v; ++i) d[i] = -inf;
        d[s] = 0;
        while (true) {
            bool update = false;
            for (int i = 0; i < e; ++i) {
                edge2 e2 = es[i];

                if (d[e2.from] != inf && d[e2.to] > d[e2.from] + e2.cost) {
                    d[e2.to] = d[e2.from] + e2.cost;
                    update = true;
                }
            }
            if (!update) break;
        }
        return vl(d);
    }

    bool find_negative_loop() {
        for (int i = 0; i < v; ++i) d[i] = 0;

        for (ll i = 0; i < v; ++i) {
            for (ll j = 0; j < e; ++j) {
                edge2 e2 = es[j];
                if (d[e2.to] > d[e2.from] + e2.cost) {
                    d[e2.to] = d[e2.from] + e2.cost;

                    if (i == v - 1) return true;
                }
            }
        }
    }


    // pは負にする
    ll dfs(vector<bool> &pass, ll now, ll times, ll score, ll p) {
        seen[now] = true;

        each(e, table[now]) {
            if (pass[e.to]) {
                if (seen[e.to]) {
                    if (score + e.cost - scores[e.to] < p) return -1;
                }

                if (score + e.cost - p * (times + 1) < scores[e.to]) {
                    scores[e.to] = score + e.cost - p * (times + 1);
                    dfs(pass, e.to, times + 1, score + e.cost, p);
                }
            }
        }
    }

    ll getscore() {
        return scores[v - 1];
    }
};


vector<bool> pass(2500);

int main() {
#ifdef MY_DEBUG
    while (true) {
#endif
        ll n, m, p;
        cin >> n >> m >> p;
        DAG dag(2500, 5000);
        DAG dag2(2500, 5000);
        rep(i, m) {
            ll a, b, c;
            cin >> a >> b >> c;
            a--, b--;
            dag.add(b, a, -c);
            dag2.add(a, b, -c);
        }
        vl d = dag.bellman_ford(0);
        vl d_rev = dag2.bellman_ford(n - 1);


        for (ll i = 0; i < n; ++i) {
            if (d[i] != -inf && d_rev[i] != -inf) pass[i] = true;
        }

        ll tmp = dag.dfs(pass, 0, 0, 0, -p);
        if (tmp == -1) cout << -1 << endl;
        else cout << -dag.getscore() << endl;

#ifdef MY_DEBUG
    }
#endif
    return 0;
}

Compiler output:
In file included from /usr/include/c++/14/bits/stl_tempbuf.h:61,
                 from /usr/include/c++/14/bits/stl_algo.h:69,
                 from /usr/include/c++/14/algorithm:61,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_construct.h: In instantiation of 'void std::_Construct(_Tp*, _Args&& ...) [with _Tp = edge2; _Args = {}]':
/usr/include/c++/14/bits/stl_uninitialized.h:643:18:   required from 'static _ForwardIterator std::__uninitialized_default_n_1<_TrivialValueType>::__uninit_default_n(_ForwardIterator, _Size) [with _ForwardIterator = edge2*; _Size = long unsigned int; bool _TrivialValueType = false]'
  643 |                 std::_Construct(std::__addressof(*__cur));
      |                 ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_uninitialized.h:712:20:   required from '_ForwardIterator std::__uninitialized_default_n(_ForwardIterator, _Size) [with _ForwardIterator = edge2*; _Size = long unsigned int]'
  710 |       return __uninitialized_default_n_1<__is_trivial(_ValueType)
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  711 |                                          && __can_fill>::
      |                                          ~~~~~~~~~~~~~~~~
  712 |         __uninit_default_n(__first, __n);
      |         ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_uninitialized.h:779:44:   required from '_ForwardIterator std::__uninitialized_default_n_a(_ForwardIterator, _Size, allocator<_Tp>&) [with _ForwardIterator = edge2*; _Size = long unsigned int; _Tp = edge2]'
  779 |     { return std::__uninitialized_default_n(__first, __n); }
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/14/bits/vector.tcc:821:35:   required from 'void std::vector<_Tp, _Alloc>::_M_default_append(size_type) [with _Tp = edge2; _Alloc = std::allocator<edge2>; size_type = long unsigned int]'
  821 |                 std::__uninitialized_default_n_a(this->_M_impl._M_finish,
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
  822 |                                                  __n, _M_get_Tp_allocator());
      |                                                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_vector.h:1016:4:   required from 'void std::vector<_Tp, _Alloc>::resize(size_type) [with _Tp = edge2; _Alloc = std::allocator<edge2>; size_type = long unsigned int]'
 1016 |           _M_default_append(__new_size - size());
      |           ^~~~~~~~~~~~~~~~~
a.cc:72:18:   required from here
   72 |         es.resize(e);
      |         ~~~~~~~~~^~~
/usr/include/c++/14/bits/stl_construct.h:119:7: error: no matching function for call to 'edge2::edge2()'
  119 |       ::new((void*)__p) _Tp(std::forward<_Args>(__args)...);
      |       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:50:5: note: candidate: 'edge2::edge2(ll, ll, ll)'
   50 |     edge2(ll from, ll to, ll cost) : from(from), to(to), cost(cost) {};
      |     ^~~~~
a.cc:50:5: note:   candidate expects 3 arguments, 0 provided
a.cc:45:8: note: candidate: 'constexpr edge2::edge2(const edge2&)'
   45 | struct edge2 {
      |        ^~~~~
a.cc:45:8: note:   candidate expects 1 argument, 0 provided
a.cc:45:8: note: candidate: 'constexpr edge2::edge2(edge2&&)'
a.cc:45:8: note:   candidate expects 1 argument, 0 provided
a.cc: In member function 'll DAG::dfs(std::vector<bool>&, ll, ll, ll, ll)':
a.cc:188:5: warning: control reaches end of non-void function [-Wreturn-type]
  188 |     }
      |     ^