Cod sursa(job #3226615)

Utilizator TeodorLuchianovTeo Luchianov TeodorLuchianov Data 22 aprilie 2024 11:38:16
Problema Floyd-Warshall/Roy-Floyd Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>

using namespace std;

ifstream in("royfloyd.in");
ofstream out("royfloyd.out");

int const INF = 1e9+7;

int const NMAX = 100;
int dist[1 + NMAX][1 + NMAX];

void computeFloyd(int n) {
  for(int k = 1;k <= n;k++) {
    for(int i = 1;i <= n;i++) {
      for(int j = 1;j <= n;j++) {
        if(dist[i][k] + dist[k][j] < dist[i][j]) {
          dist[i][j] = dist[i][k] + dist[k][j];
        }
      }
    }
  }
}

int main() {

  int n;
  in >> n;
  for(int i = 1;i <= n;i++) {
    for(int j = 1;j <= n;j++) {
      in >> dist[i][j];
      if(i != j && dist[i][j] == 0) {
        dist[i][j] = INF;
      }
    }
  }
  computeFloyd(n);
  for(int i = 1;i <= n;i++) {
    for(int j = 1;j <= n;j++) {
      if(dist[i][j] == INF) {
        out << "0 ";
      }else {
        out << dist[i][j] << ' ';
      }
    }
    out << '\n';
  }
  return 0;
}