high_score

mail@pastecode.io avatar
unknown
c_cpp
a month ago
1.1 kB
2
Indexable
Never
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

#define sortpartial(li, a, b) sort(li.begin()+a, li.begin()+b)
#define ip(num) ll num;cin >> num
#define print(v) for(auto i:v)cout<<i<<" ";cout<<endl
#define fast_io \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL);

int main()
{
    fast_io;
    ip(n); ip(m);
    vector<vector<int>> adj;
    vector<ll> dist(n+1, LLONG_MIN);
    for (ll i = 0; i < m; i++)
    {
        ip(node1); ip(node2); ip(weight);
        adj.push_back({node1, node2, weight});
    }

    dist[1] = 0;
    for(int i = 0; i < n; i++){
        for(auto j : adj){
            if(dist[j[0]] != LLONG_MIN && dist[j[0]] + j[2] > dist[j[1]]){
                dist[j[1]] = dist[j[0]] + j[2];
            }
        }
    }
    int f = 0;
    for(auto j : adj){
        if(dist[j[0]] != LLONG_MIN && dist[j[0]] + j[2] > dist[j[1]]){
            dist[j[1]] = dist[j[0]] + j[2];
            if(j[1] == n)f = 1;
        }
    }

    if(!f){
        cout << dist[n] << endl;
    }
    else{
        cout << -1 << endl;
    }
    
}
Leave a Comment