high_score
unknown
c_cpp
a year ago
1.1 kB
5
Indexable
#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; } }
Editor is loading...
Leave a Comment