SHARE
TWEET

Untitled

a guest Jul 17th, 2019 74 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <queue>
  5. using namespace std;
  6.  
  7. #define int long long
  8.  
  9. int n, d[2500][2500], x[2500][2500];
  10. const long long INF = 1e15 + 999;
  11.  
  12. signed main()
  13. {
  14.     ios_base::sync_with_stdio(false);
  15.     cin.tie(0);
  16.     cout.tie(0);
  17.     cin >> n;
  18.     for (int i = 0; i < n; ++i) {
  19.         for (int j = 0; j < n; ++j) {
  20.             cin >> x[i][j];
  21.         }
  22.     }
  23.     for (int i = 0; i < n; ++i) {
  24.         for (int j = 0; j < n; ++j) {
  25.             if (i == j) {
  26.                 d[i][j] = 0;
  27.             }
  28.             else {
  29.                 if (x[i][j] != 0) {
  30.                     d[i][j] = x[i][j];
  31.                 }
  32.                 else {
  33.                     d[i][j] = INF;
  34.                 }
  35.             }
  36.         }
  37.     }
  38.     for (int k = 0; k < n; ++k) {
  39.         for (int i = 0; i < n; ++i) {
  40.             for (int j = 0; j < n; ++j) {
  41.                 if (d[i][k] == INF || d[k][j] == INF) continue;
  42.                 if (d[i][j] > d[i][k] + d[k][j]) {
  43.                     d[i][j] = d[i][k] + d[k][j];
  44.                 }
  45.             }
  46.         }
  47.     }
  48.     for (int k = 0; k < n; ++k) {
  49.         for (int i = 0; i < n; ++i) {
  50.             for (int j = 0; j < n; ++j) {
  51.                 if (d[k][k] < 0 && d[i][k] != INF && d[k][j] != INF) {
  52.                     d[i][j] = -INF;
  53.                 }
  54.             }
  55.         }
  56.     }
  57.     for (int i = 0; i < n; ++i) {
  58.         for (int j = 0; j < n; ++j) {
  59.             if (d[i][j] == -INF) {
  60.                 cout << 2 << " ";
  61.             }
  62.             else {
  63.                 if (d[i][j] < 1e15) {
  64.                     cout << 1 << " ";
  65.                 }
  66.                 else {
  67.                     cout << 0 << " ";
  68.                 }
  69.             }
  70.         }
  71.         cout << endl;
  72.     }
  73. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top