Cod sursa(job #668187)

Utilizator OanaCristinaFlorescu Oana Cristina OanaCristina Data 24 ianuarie 2012 15:34:09
Problema Floyd-Warshall/Roy-Floyd Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include<iostream>
#include<fstream>
using namespace std;
ifstream in("royfloyd.in");
ofstream out("royfloyd.out");

int A[101][101],n;

int main()
{
	int dt;
	in>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			in>>A[i][j];
	int infinit=200000;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(A[i][j]==0)
				A[i][j]=infinit;
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(k!=i && k!=j && i!=j)
				{
					dt=A[i][k]+A[k][j];
					if(dt<A[i][j])
						A[i][j]=dt;
				}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(A[i][j]==infinit)
				A[i][j]=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
			out<<A[i][j]<<" ";
		out<<endl;
	}
	return 0;
}