Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int inf = 100000;
- int n;
- vector<vector<int>> dp;
- int main(){
- //freopen("allpairs.in", "r", stdin);
- cin >> n;
- dp.resize(n+1, vector<int>(n+1, inf));
- for(int i=1; i<=n; i++){
- for(int j=1; j<=n; j++){
- int a;
- cin >> a;
- dp[i][j] = a;
- }
- }
- for(int k=1; k<=n; k++){
- for(int i=1; i<=n; i++){
- for(int j=1; j<=n; j++){
- dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]);
- }
- }
- }
- for(int i=1; i<=n; i++){
- if(dp[i][i]<0){
- cout << "No Solution" << '\n';
- return 0;
- }
- }
- for(int i=1; i<=n; i++){
- string s;
- for(int j=1; j<=n; j++){
- cout << s << dp[i][j];
- s = " ";
- }
- cout << '\n';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement