Advertisement
Little_hobbit

Алгоритм Флойда - Графы

Jul 7th, 2020
178
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.05 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int main( )
  6. {
  7.     int n;
  8.     cin >> n;
  9.    
  10.     // Матрица расстояний графа
  11.     int d[n][n];
  12.     // Ввод графа
  13.     for (int i = 0; i < n; ++i)
  14.     {
  15.         for (int j = 0; j < n; ++j)
  16.         {
  17.             cin >> d[i][j];
  18.  
  19.             if (i != j && !d[i][j])
  20.                 d[i][j] = INT32_MAX;
  21.         }
  22.     }
  23.  
  24.     // Расчет минимального расстояния
  25.     for (int k = 0; k < n; ++k)
  26.     {
  27.         for (int i = 0; i < n; ++i)
  28.         {
  29.             for (int j = 0; j < n; ++j)
  30.             {
  31.                 if (d[i][k] < INT32_MAX && d[k][j] < INT32_MAX)
  32.                     d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
  33.             }
  34.         }
  35.     }
  36.  
  37.     // Вывод графа
  38.     for (int i = 0; i < n; ++i)
  39.     {
  40.         for (int j = 0; j < n; ++j)
  41.         {
  42.             if (d[i][j] == INT32_MAX)
  43.                 cout << "x ";
  44.             else
  45.                 cout << d[i][j] << ' ';
  46.         }
  47.         cout << endl;
  48.     }
  49.  
  50.     return 0;
  51. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement