Cod sursa(job #1726233)
Utilizator | Solcan Mihai Andrei SolcanMihai | Data | 7 iulie 2016 15:55:23 |
---|---|---|---|
Problema | Floyd-Warshall/Roy-Floyd | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.44 kb |
#include <cstdio>
using namespace std;
int n;
int mat[105][105];
const int MAX_INT = 1010;
void citire()
{
int tmp;
scanf("%d", &n);
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
scanf("%d", &tmp);
mat[i][j] = tmp;
if(mat[i][j] == 0)
{
mat[i][j] = MAX_INT;
}
}
}
}
void royfloyd()
{
for(int k = 0; k < n; k++)
{
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(i != n && j != n)
{
if(mat[k][j] + mat[i][k] < mat[i][j])
{
mat[i][j] = mat[k][j] + mat[i][k];
}
}
}
}
}
}
void afisare()
{
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(i == j)
{
printf("0 ");
continue;
}
if(mat[i][j] == MAX_INT)
{
printf("0 ");
continue;
}
printf("%d ", mat[i][j]);
}
printf("\n");
}
}
int main()
{
freopen("royfloyd.in", "r", stdin);
freopen("royfloyd.out", "w", stdout);
citire();
royfloyd();
afisare();
return 0;
}