Language: C++

#ifndef __GRAPH_H__
#define __GRAPH_H__

#include <vector>
#include <cstdint>

struct GraphEdge {
	int from = 0;
	int to = 0;

	GraphEdge() = default;
	GraphEdge(int from, int to);
};

class Graph {
public:
	using EdgeID = int;
	using Edge = GraphEdge;
	using List = std::vector<EdgeID>;

private:
	std::vector<List> ids;
 	std::vector<Edge> edges;

public:
	Graph() = default;
	Graph(Graph&&) = default;
	Graph(const Graph&) = default;
	Graph& operator=(Graph&&) = default;
	Graph& operator=(const Graph&) = default;

	Graph(int size);
	int size() const;
	void resize(int new_size);

	void add(int from, int to);
	const Edge& getEdge(EdgeID id) const;
	const List& row(int from) const;
};

#endif

#ifdef ONLY_MY_ENVIR
#include "Graph.h"
#endif

#include <cassert>

GraphEdge::GraphEdge(int from, int to)
	: from(from), to(to) {
}

Graph::Graph(int size) 
	: ids(size) {
}

int Graph::size() const {
	return ids.size();
}

void Graph::resize(int new_size) {
	assert(new_size >= size());
	ids.resize(new_size);
}

void Graph::add(int from, int to) {
	ids[from].push_back(edges.size());
	edges.push_back(Edge(from, to));
}

const Graph::Edge& Graph::getEdge(EdgeID id) const {
	assert(id >= 0 && id < edges.size());
	return edges[id];
}

const Graph::List& Graph::row(int from) const {
	return ids[from];
}

#ifndef __SHORTEST_H__
#define __SHORTEST_H__

#ifdef ONLY_MY_ENVIR
#include "Graph.h"
#endif

#include <vector>

struct DijkstraResult {
	std::vector<int64_t> distance;
	std::vector<int> previous;
};

struct BellmanFordResult {
	std::vector<int64_t> distance;
	std::vector<int> previous;
	std::vector<bool> is_unbounded;		// 始点からの距離がいくらでも小さくなる(この場合 distance と previous の値は意味を持たない)
};

DijkstraResult dijkstra(const Graph& graph, const std::vector<int64_t>& costs, int start);
BellmanFordResult bellmanFord(const Graph& graph, const std::vector<int64_t>& costs, int start);


#endif


#ifdef ONLY_MY_ENVIR
#include "Shortest.h"
#endif

#include <queue>
#include <utility>
#include <limits>
#include <algorithm>

/* ダイクストラ法により単一始点最短路を求める O(m log n) */
DijkstraResult dijkstra(const Graph& graph, const std::vector<int64_t>& costs, int start) {
	struct State {
		int64_t dist;
		int vertex;

		State(int dist, int vertex)
			: dist(dist), vertex(vertex) {
		}

		// 順序を逆転させる
		bool operator<(const State& right) const {
			return dist > right.dist;
		}
	};

	constexpr int64_t Infinity = std::numeric_limits<int64_t>::max();
	const int size = graph.size();

	std::vector<int64_t> distance(size, Infinity);
	std::vector<int> previous(size, -1);

	std::priority_queue<State> que;
	distance[start] = 0;
	que.push(State(int64_t(), start));

	while (!que.empty()) {
		const State state = que.top();
		que.pop();

		const int64_t dist = state.dist;
		const int from = state.vertex;

		if (dist > distance[from]) continue;

		for (int id : graph.row(from)) {
			const auto& edge = graph.getEdge(id);
			const int to = edge.to;
			const int64_t cost = costs[id];
			const int64_t dist_new = dist + cost;

			if (dist_new >= distance[to]) continue;

			distance[to] = dist_new;
			previous[to] = from;
			que.push(State(dist_new, to));
		}
	}

	DijkstraResult result;
	result.distance = std::move(distance);
	result.previous = std::move(previous);
	return result;
}

/* ベルマンフォード法により単一始点最短路を求める O(nm) */
/* 負閉路検出には別の関数を使う: TODO */
BellmanFordResult bellmanFord(const Graph& graph, const std::vector<int64_t>& costs, int start) {
	constexpr int64_t Infinity = std::numeric_limits<int64_t>::max();
	const int size = graph.size();

	std::vector<int64_t> distance(size, Infinity);
	std::vector<int> previous(size, -1);
	std::vector<bool> is_unbounded(size, false);

	distance[start] = int64_t();

	// 始点からの距離を更新
	auto update = [size, Infinity, &graph, &costs](std::vector<int64_t>& distance, std::vector<int>& previous) -> void {
		for (int from = 0; from < size; ++from) {
			if (distance[from] == Infinity) continue;
			for (int id : graph.row(from)) {
				const auto& edge = graph.getEdge(id);
				const int to = edge.to;
				const int64_t cost = costs[id];

				if (distance[from] + cost < distance[to]) {
					distance[to] = distance[from] + cost;
					previous[to] = from;
				}
			}
		}
	};
	
	// 負閉路を検出(あれば is_unbounded を true とする)
	auto detect = [size, Infinity, &graph, &costs](std::vector<int64_t>& distance, std::vector<bool>& is_unbounded) -> void {
		for (int from = 0; from < size; ++from) {
			if (distance[from] == Infinity) continue;
			for (int id : graph.row(from)) {
				const auto& edge = graph.getEdge(id);
				const int to = edge.to;
				const int64_t cost = costs[id];

				if (distance[from] + cost < distance[to]) {
					is_unbounded[from] = true;
					break;
				}
			}
		}
	};

	// 負閉路を伝搬
	auto propagate = [size, Infinity, &graph, &distance](std::vector<bool>& is_unbounded) -> void {
		for (int from = 0; from < size; ++from) {
			if (distance[from] == Infinity) continue;
			if (!is_unbounded[from]) continue;
			for (int id : graph.row(from)) {
				const auto& edge = graph.getEdge(id);
				const int to = edge.to;
				is_unbounded[to] = true;
			}
		}
	};

	for (int z = 1; z < size; ++z) {
		update(distance, previous);
	}

	detect(distance, is_unbounded);

	for (int z = 1; z < size; ++z) {
		propagate(is_unbounded);
	}

	BellmanFordResult result;
	result.distance = std::move(distance);
	result.previous = std::move(previous);
	result.is_unbounded = std::move(is_unbounded);
	return result;
}

#define _CRT_SECURE_NO_WARNINGS
#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <array>

#ifdef ONLY_MY_ENVIR
#include "Shortest.h"
#endif

using namespace std;

int main() {
	int n, m, r;
	scanf("%d %d %d", &n, &m, &r);

	Graph g(n);
	std::vector<int64_t> costs;
	for (int j = 0; j < m; ++j) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		--a; --b;
		g.add(a, b);
		costs.push_back(r - c);
	}

	auto res = bellmanFord(g, costs, 0);
	if (res.is_unbounded[n - 1]) {
		puts("-1");
	} else {
		printf("%lld\n", max(0ll, -res.distance[n - 1]));
	}

	return 0;
}


Compiler output:
a.cc: In function 'int main()':
a.cc:281:37: error: no matching function for call to 'max(long long int, __gnu_cxx::__alloc_traits<std::allocator<long int>, long int>::value_type)'
  281 |                 printf("%lld\n", max(0ll, -res.distance[n - 1]));
      |                                  ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/vector:62,
                 from a.cc:4:
/usr/include/c++/14/bits/stl_algobase.h:257:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  257 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:257:5: note:   template argument deduction/substitution failed:
a.cc:281:37: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and '__gnu_cxx::__alloc_traits<std::allocator<long int>, long int>::value_type' {aka 'long int'})
  281 |                 printf("%lld\n", max(0ll, -res.distance[n - 1]));
      |                                  ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:303:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  303 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:303:5: note:   candidate expects 3 arguments, 2 provided
In file included from /usr/include/c++/14/algorithm:61,
                 from a.cc:114:
/usr/include/c++/14/bits/stl_algo.h:5706:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)'
 5706 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5706:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5716:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)'
 5716 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5716:5: note:   template argument deduction/substitution failed:
a.cc:281:37: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  281 |                 printf("%lld\n", max(0ll, -res.distance[n - 1]));
      |                                  ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~