Advertisement
Guest User

Untitled

a guest
Jan 23rd, 2017
115
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.91 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define inf 1000000000
  3. #define intt long long
  4.  
  5. using namespace std ;
  6.  
  7. intt a , b , weight[11112][11112] , n , m , w ,adj[11112][11112] , d[11112] , p[11112] ;
  8.  
  9. void initialize ( int s )
  10. {
  11.      
  12.     for ( intt i = 1 ; i <= n ; i ++ )
  13.     {
  14.          
  15.         d[i] = inf ;
  16.          
  17.         d[s] = 0 ;
  18.          
  19.     }
  20.      
  21. }  
  22.  
  23. void relax ( intt u , intt v )
  24. {
  25.      
  26.     if ( d[v] > d[u] + weight[u][v] )
  27.     {
  28.          
  29.         d[v] = d[u] + weight[u][v] ;
  30.          
  31.         p[v] = u ;
  32.          
  33.     }
  34.      
  35. }
  36.  
  37. void Bellman_Ford ( int s )
  38. {
  39.      
  40.     initialize ( s ) ;
  41.      
  42.     for ( intt k = 1 ; k < n ; k ++ )
  43.     {
  44.          
  45.         for ( intt i = 1 ; i <= n ; i ++ )
  46.          
  47.             for ( intt j = 1 ; j <= n ; j ++ )
  48.             {
  49.                 if ( adj[i][j] == 1 )
  50.                  
  51.                 relax ( i , j ) ;
  52.                      
  53.         }
  54.          
  55.     }
  56.      
  57. }
  58.  
  59. bool negativeCycle ()
  60.  
  61.      
  62.     for ( intt i = 1 ; i <= n ; i ++ )
  63.     {
  64.          
  65.         for ( intt j = 1 ; j <= n ; j ++ )
  66.         {
  67.              
  68.             if ( adj[i][j] == 1 && d[j] > d[i] + weight[i][j] )
  69.              
  70.                 return true ;
  71.                  
  72.         }
  73.          
  74.     }
  75.      
  76.     return false ;
  77.      
  78. }
  79.  
  80. int main ()
  81. {
  82.      
  83.     cin >> n >> m ;
  84.      
  85.     while ( m -- )
  86.     {
  87.          
  88.         cin >> a >> b >> w ;
  89.          
  90.         if ( adj[a][b] == 1 )
  91.         {
  92.              
  93.             weight[a][b] = min ( w , weight[a][b] ) ;
  94.              
  95.             continue ;
  96.              
  97.         }
  98.          
  99.         adj[a][b] = 1 ;
  100.          
  101.         weight[a][b] = w ;
  102.          
  103.     }
  104.      
  105.     Bellman_Ford ( 1 ) ;
  106.      
  107.     if ( negativeCycle () == true ) cout << "yes" << endl ;
  108.      
  109.     else cout << "no" << endl ;
  110.      
  111.     return 0 ;
  112.      
  113. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement