Advertisement
tepyotin2

All-pairs Shortest Path

May 31st, 2025
96
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.71 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int inf = 100000;
  6.  
  7. int n;
  8. vector<vector<int>> dp;
  9.  
  10. int main(){
  11.     //freopen("allpairs.in", "r", stdin);
  12.    
  13.     cin >> n;
  14.     dp.resize(n+1, vector<int>(n+1, inf));
  15.     for(int i=1; i<=n; i++){
  16.         for(int j=1; j<=n; j++){
  17.             int a;
  18.             cin >> a;
  19.             dp[i][j] = a;
  20.         }
  21.     }
  22.     for(int k=1; k<=n; k++){
  23.         for(int i=1; i<=n; i++){
  24.             for(int j=1; j<=n; j++){
  25.                 dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]);
  26.             }
  27.         }
  28.     }
  29.     for(int i=1; i<=n; i++){
  30.         if(dp[i][i]<0){
  31.             cout << "No Solution" << '\n';
  32.             return 0;
  33.         }
  34.     }
  35.     for(int i=1; i<=n; i++){
  36.         string s;
  37.         for(int j=1; j<=n; j++){
  38.             cout << s << dp[i][j];
  39.             s = " ";
  40.         }
  41.         cout << '\n';
  42.     }
  43.    
  44.     return 0;
  45. }
  46.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement