SHARE
TWEET

Untitled

Rentib Feb 17th, 2020 65 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main(){
  4.   int n, m;
  5.   cin >> n >> m;
  6.   int d[n + 7][n + 7];
  7.   for(int i = 1;i <= n;i++){
  8.     for(int j = 1;j <= n;j++){
  9.       d[i][j] = INT_MAX;
  10.       if(i == j)
  11.         d[i][j] = 0;;
  12.     }
  13.   }
  14.   for(int i = 0, a, b, c;i < m;i++){
  15.     cin >> a >> b >> c;
  16.     d[a][b] = c;
  17.   }
  18.   for(int k = 1;k <= n;k++){
  19.     for(int j = 1;j <= n;j++){
  20.       for(int i = 1;i <= n;i++){
  21.         if(d[i][k] < INT_MAX && d[k][j] < INT_MAX)
  22.           d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
  23.       }
  24.     }
  25.   }
  26.   for(int i = 1;i <= n;i++){
  27.     for(int j = 1;j <= n;j++){
  28.       for(int t = 1;t <= n;t++){
  29.         if(d[i][t] < INT_MAX && d[t][t] < 0 && d[t][j] < INT_MAX)
  30.           d[i][j] = INT_MIN;
  31.       }
  32.     }
  33.   }
  34.   for(int i = 1;i <= n;i++){
  35.     for(int j = 1;j <= n;j++){
  36.       if(d[i][j] == INT_MAX) cout << "* ";
  37.       else if(d[i][j] == INT_MIN) cout << "-oo ";
  38.       else if(i == j) cout << min(0, d[i][j]) << ' ';
  39.       else cout << d[i][j] << ' ';
  40.     }
  41.     cout << '\n';
  42.   }
  43. }
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