Pagini recente » Cod sursa (job #213435) | Cod sursa (job #2679289) | Cod sursa (job #2986949) | Cod sursa (job #2037378) | Cod sursa (job #452281)
Cod sursa(job #452281)
# include <cstdio>
using namespace std;
# define FIN "royfloyd.in"
# define FOUT "royfloyd.out"
# define inf 0x3f3f3f3f
# define MAX_N 105
int N, val, i, j;
int D[MAX_N][MAX_N];
void roy_floyd() {
int i, j, k;
for (k = N; k >= 1; --k)
for (i = 1; i <= N; ++i)
for (j = 1; j <= N; ++j)
if (i != j && D[i][j] > D[i][k] + D[k][j]) D[i][j] = D[i][k] + D[k][j];
}
int main() {
freopen(FIN, "r", stdin);
freopen(FOUT, "w", stdout);
scanf("%d", &N);
for (i = 1; i <= N; ++i)
for (j = 1; j <= N; ++j) {
scanf("%d", &val);
if (i == j) { D[i][j] = 0; continue; }
D[i][j] = (!val ? inf : val);
}
roy_floyd();
for (i = 1; i <= N; ++i)
for (j = 1; j <= N; ++j)
if (D[i][j] == inf) D[i][j] = 0;
for (i = 1; i <= N; ++i) {
for (j = 1; j <= N; ++j)
printf("%d ", D[i][j]);
printf("\n");
}
return 0;
}