Лабиринт знаний. Графы

Входные данные
2 2
1 2 5
1 2 -5

Выходные данные
5

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long  ll;
typedef unsigned long long ull;
typedef map <int, int> mii;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
 
int const maxn = int(1e5 + 12);
int const maxb = int(2e6 + 12);
int const inf = int(1e9 + 7);
ll const linf = ll(1e18 + 12);
double const eps = 1e-7;
double const pi = acos(-1);
#ifdef _WIN32
    #define I64 "%I64d"
#else
    #define I64 "%lld"
#endif
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define next MyLittleNext
//#define end MyLittleEnd
#define all(x) x.begin(), x.end()
#define LOCAL
 
struct edge
{
    int a, b, c;
    edge(int a, int b, int c) : a(a), b(b), c(c) {};
};
 
int n, m;
vector <edge> e;
vector <int> g[maxn];
int us[maxn];
 
void dfs(int v)
{
    us[v] = 1;
    for (int i = 0; i < int(g[v].size()); i++)
    {
        int to = g[v][i];
        if (!us[to])
            dfs(to);
    }
}
 
int main()
{
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a].pb(b);
        e.pb(edge(a, b, -c));
    }
    vector <int> d(n + 1, inf);
    d[1] = 0;
    int x = -1;
    for (int i = 0; i < n; i++)
    {
        x = -1;
        for (int j = 0; j < m; j++)
            if (d[e[j].a] < inf && d[e[j].b] > d[e[j].a] + e[j].c)
            {
                d[e[j].b] = max(-inf, d[e[j].a] + e[j].c);
                x = e[j].b;
            }
        //printf("%d ", x);
    }
    if (x != -1)
        dfs(x);
    if (us[n])
    {
        puts(":)");
        return 0;
    }
    if (d[n] >= inf)
    {
        puts(":(");
        return 0;
    }
    printf("%d", -d[n]);
}

#include<bits/stdc++.h>
#define int long long
#define inf 1e10l
using namespace std;
 
 
struct edge { int u, v, c; };
vector<pair<int, int>> gp[2002];
vector<edge> g;
vector<int> d(2002, -inf), p(2002, -1), used(2002, 0), ban(2002, 0);
 
void bfs(int i, int c) {
    used[i] = c;
    for (auto& e : gp[i]) {
        if (!used[e.first]) bfs(e.first, c);
    }
}
 
int32_t main() {
    ifstream cin("input.txt");
    int n, m; cin >> n >> m;
 
    for (int i = 0; i < m; i++) {
        edge ins; cin >> ins.u >> ins.v >> ins.c;
        ins.u--; ins.v--;
        gp[ins.v].push_back(make_pair(ins.u, ins.c));
        g.push_back(ins);
    }
    d[0] = 0;
    for (int k = 0; k < n; k++) {
        for (auto& e : g) {
            if (d[e.u] > -inf && d[e.v] < d[e.u] + e.c) {
                d[e.v] = d[e.u] + e.c;
                p[e.v] = e.u;
            }
        }
    }
     
    if (d[n - 1] == -inf) {
        cout << ":(";
        return 0;
    }
    bfs(n - 1, 1);                  
 
    int u = 2002;
    while (u != -1) {
        u = -1;
        for (auto& e : g) {
            if (!ban[e.u] && !ban[e.v]) {
                if (d[e.u] > -inf && d[e.v] < d[e.u] + e.c) {
                    d[e.v] = d[e.u] + e.c;
                    p[e.v] = e.u;
                    u = e.u;
                }
            }
        }
        if (u == -1) continue;
        vector<int> cyc; 
        int y = u;
        for (int i = 0; i < n; i++) {
            y = p[y];
        }
        for (int cur = y; ; cur = p[cur]) {
            cyc.push_back(cur);
            if (cur == y && cyc.size() > 1)  break;
        }
        for (auto b : cyc) ban[b] = 1;
    }
 
    for (int i = 0; i < n; i++) {
        if (used[i] && ban[i]) {
            cout << ":)"; return 0;
        }
    }
    cout << d[n - 1];
    return 0;
}

using MyType=int64_t;

typedef std::pair<int, int> pair_int;       // псевдонимы типов делают код более читабельным
typedef std::vector< pair_int>  vec_of_pair;  // и более гибким для изменения.
std::vector<vec_of_pair> gp(2002, vec_of_pair()); // также желательно вынести литерал 2002 в константу

std::vector<std::vector< std::pair<int, int>>> gp(2002, std::vector< std::pair<int, int>>());