kananasgarli90

Floyd

Oct 24th, 2020
404
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;
  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.                 dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
  10.             }
  11.         }
  12.     }
  13. }
  14. int main()
  15. {
  16.     cin>>n;
  17.     for(int i = 1; i <= n; i++){
  18.         for(int j = 1; j <= n; j++){
  19.             cin>>dis[i][j];
  20.             if(dis[i][j] == -1){
  21.                 dis[i][j] = INF;
  22.             }
  23.         }
  24.     }
  25.     FloydWarshall();
  26.     int maks = -INF;
  27.     for(int i = 1; i <= n; i++){
  28.         for(int j = 1; j <= n; j++){
  29.             if(dis[i][j] != INF){
  30.                 maks = max(maks, dis[i][j]);
  31.             }
  32.         }
  33.     }
  34.     cout<<maks<<endl;
  35. }
  36.  
RAW Paste Data