kananasgarli90

Floyd-yasama

Oct 24th, 2020
452
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define INF 1000000000
  4. int dis[101][101], n, a[101][101];
  5. void FloydWarshall(){
  6.     for(int k = 1; k <= n; k++){
  7.         for(int i = 1; i <= n; i++){
  8.             for(int j = 1; j <= n; j++){
  9.                 if(dis[i][k] != INF && dis[k][j] != INF){
  10.                     dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
  11.                 }
  12.             }
  13.         }
  14.     }
  15.  
  16.     for(int k = 1; k <= n; k++){
  17.         for(int i = 1; i <= n; i++){
  18.             a[k][i] = 1;
  19.             if(dis[k][i] == INF){
  20.                 a[k][i] = 0;
  21.                 continue;
  22.             }
  23.             for(int j = 1; j <= n; j++){
  24.                 if((dis[j][j] < 0 || dis[i][i] < 0 || dis[k][k] < 0 )&&
  25.                     dis[i][k] != INF && dis[k][j] != INF){
  26.                     a[i][k] = a[k][j] = a[i][j] = 2;
  27.                 }
  28.             }
  29.         }
  30.     }
  31.  
  32. }
  33. int main()
  34. {
  35.     cin>>n;
  36.     for(int i = 1; i <= n; i++){
  37.         for(int j = 1; j <= n; j++){
  38.             cin>>dis[i][j];
  39.             if(i != j && dis[i][j] == 0){
  40.                 dis[i][j] = INF;
  41.             }
  42.         }
  43.     }
  44.     FloydWarshall();
  45.     for(int i = 1; i <= n; i++){
  46.         for(int  j = 1; j < n; j++){
  47.             cout<<a[i][j]<<" ";
  48.         }
  49.         cout<<a[i][n]<<endl;
  50.     }
  51. }
  52.  
RAW Paste Data