Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define inf 1000000000
- #define intt long long
- using namespace std ;
- intt a , b , weight[11112][11112] , n , m , w ,adj[11112][11112] , d[11112] , p[11112] ;
- void initialize ( int s )
- {
- for ( intt i = 1 ; i <= n ; i ++ )
- {
- d[i] = inf ;
- d[s] = 0 ;
- }
- }
- void relax ( intt u , intt v )
- {
- if ( d[v] > d[u] + weight[u][v] )
- {
- d[v] = d[u] + weight[u][v] ;
- p[v] = u ;
- }
- }
- void Bellman_Ford ( int s )
- {
- initialize ( s ) ;
- for ( intt k = 1 ; k < n ; k ++ )
- {
- for ( intt i = 1 ; i <= n ; i ++ )
- for ( intt j = 1 ; j <= n ; j ++ )
- {
- if ( adj[i][j] == 1 )
- relax ( i , j ) ;
- }
- }
- }
- bool negativeCycle ()
- for ( intt i = 1 ; i <= n ; i ++ )
- {
- for ( intt j = 1 ; j <= n ; j ++ )
- {
- if ( adj[i][j] == 1 && d[j] > d[i] + weight[i][j] )
- return true ;
- }
- }
- return false ;
- }
- int main ()
- {
- cin >> n >> m ;
- while ( m -- )
- {
- cin >> a >> b >> w ;
- if ( adj[a][b] == 1 )
- {
- weight[a][b] = min ( w , weight[a][b] ) ;
- continue ;
- }
- adj[a][b] = 1 ;
- weight[a][b] = w ;
- }
- Bellman_Ford ( 1 ) ;
- if ( negativeCycle () == true ) cout << "yes" << endl ;
- else cout << "no" << endl ;
- return 0 ;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement