high_score_1673.cpp (1226B)
1 #include <algorithm> 2 #include <iostream> 3 #include <tuple> 4 #include <vector> 5 6 constexpr long long inf = 999999999999999LL; 7 8 size_t findcycle( 9 size_t v, 10 const std::vector<std::tuple<size_t, size_t, long long>>& a, 11 const std::vector<size_t>& p 12 ) { 13 std::vector<bool> visited(p.size(), false); 14 visited[v] = true; 15 size_t u = p[v]; 16 while (!visited[u]) { 17 visited[u] = true; 18 u = p[u]; 19 } 20 return u; 21 } 22 23 int main() { 24 size_t n, m; 25 std::cin >> n >> m; 26 std::vector<std::tuple<size_t, size_t, long long>> a(m); 27 for (size_t i = 0; i < m; i++) { 28 size_t x, y; 29 long long w; 30 std::cin >> x >> y >> w; 31 a[i] = {x-1, y-1, w}; 32 } 33 34 std::vector<size_t> p(n, n); 35 std::vector<long long> d(n, -inf); 36 d[0] = 0; 37 std::vector<bool> reach_1(n, false), reach_n(n, false); 38 reach_1[0] = reach_n[n-1] = true; 39 for (size_t i = 0; i < n; i++) { 40 for (auto [v, u, w] : a) { 41 if (d[u] < d[v] + w) { 42 d[u] = d[v] + w; 43 p[u] = v; 44 } 45 reach_n[v] = reach_n[v] || reach_n[u]; 46 reach_1[u] = reach_1[u] || reach_1[v]; 47 } 48 } 49 50 for (auto [v, u, w] : a) { 51 if (d[u] < d[v] + w) { 52 size_t x = findcycle(u, a, p); 53 if (reach_1[x] && reach_n[x]) { 54 std::cout << "-1\n"; 55 return 0; 56 } 57 } 58 } 59 60 std::cout << d[n-1] << "\n"; 61 }