Advertisement
Guest User

Untitled

a guest
Jun 24th, 2019
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.78 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int n, m, d[100][100], sum, sm[100], u[100];
  6. const int INF = 1e9;
  7.  
  8. void dfs(int v){
  9.     if(u[v]==2&&sum-sm[v]<0){ cout << "This graph include negative cyrcle:)"; exit(0);}
  10.     if(u[v]) return;
  11.     u[v] = 2;
  12.     for(int i = 0; i < n; ++i){
  13.         if(d[v][i]!=1e5){
  14.          sum+=d[v][i];
  15.          if(u[i]!=2) sm[i] = sm[v]+d[v][i];
  16.          dfs(i), sum-=d[v][i];
  17.          }
  18.         }
  19.     sm[v] = 0;
  20.     u[v] = 1;
  21.     }
  22.  
  23. int main(){
  24.     ios_base::sync_with_stdio(0);
  25.     cin.tie(0);
  26.     cin >> n;
  27.     for(int i = 0; i < n; ++i)
  28.         for(int j = 0; j < n; ++j){
  29.             cin >> d[i][j];
  30.             }
  31.  
  32.     for(int i = 0; i < n; ++i)
  33.         if(!u[i]) dfs(i);
  34.     cout << "Not included:(";
  35.  
  36.     return 0;
  37.     }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement