ainunsy1

Untitled

Oct 25th, 2021
713
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //author : ainunsy1
  2. #include <bits/stdc++.h>
  3. #define forn(i,a,b) for(int i=a; i<=b; i++)
  4. #define ford(i,a,b) for(int i=a; i>=b; i--)
  5. #define fi first
  6. #define se second
  7. using namespace std;
  8. typedef long long ll;
  9. const int MX=5e3+5;
  10. ll n,m,dist[MX],vis[MX];
  11. vector<tuple<ll,ll,ll>>v;
  12. vector<ll> adj[MX];
  13. void dfs(int i){
  14.     vis[i]=1;
  15.     for(auto j:adj[i])
  16.         if(!vis[j])
  17.             dfs(j);
  18. }
  19. void solve(){
  20.     dist[1]=0;
  21.     cin>>n>>m;
  22.     forn(i,2,n)
  23.         dist[i]=LLONG_MIN;
  24.     forn(i,1,m){
  25.         ll a,b,w;
  26.         cin>>a>>b>>w;
  27.         adj[a].push_back(b);
  28.         v.push_back({a,b,w});
  29.     }
  30.     forn(i,1,m){
  31.         for(auto [a,b,w]:v){
  32.             if(dist[a]!=LLONG_MIN && dist[b]<dist[a]+w)
  33.                 dist[b]=dist[a]+w;
  34.         }
  35.     }
  36.     bool ada=false,gaada=true;
  37.     for(auto [a,b,w]:v){
  38.         if(dist[a]!=LLONG_MIN && dist[b]<dist[a]+w){
  39.             memset(vis,0,sizeof(vis));
  40.             dfs(a);
  41.             ada|=(!vis[n]);
  42.             gaada&=(vis[n]);
  43.         }
  44.     }
  45.     if(ada || gaada)
  46.         cout<<dist[n]<<"\n";
  47.     else
  48.         cout<<"-1\n";
  49. }
  50. int main(){
  51.     ios::sync_with_stdio(0); cin.tie(0);
  52.     int tc=1;
  53.     // cin>>tc;
  54.     forn(i,1,tc){
  55.         solve();
  56.     }
  57. }
RAW Paste Data