/**
 * (c)2005 Tomasz Lubinski
 * www.algorytm.org
 * algorytm Floyda - minimalne odleglosci miedzy wierzcholkami
 * w grafie, domkniecie zwrotne
 * 
 */
public class Floyd {

	private static Macierz A[][];
	public static void main(String[] args) {
		
		int i,j,k,n;
		String tmp;

		System.out.println("Podaj liczbe wierzcholkow");
		n = Console.readInt("?");
		A = new Macierz[n][];
		for (i=0; i<n; i++) {
			A[i] = new Macierz[n];
			for (j=0; j<n; j++) {
				A[i][j] = new Macierz();
			}
		}
		System.out.println("Podaj wartosci macierzy odleglosci A");
		System.out.println("Gdy miedzy wierzcholkami nie ma polaczenia wpisz niesk");

		//wczytanie od uzytkownika odleglosci
		for (i=0; i<n; i++)
			for (j=0; j<n; j++) {
				if (i==j) {
					A[i][j].odl=0; 
					A[i][j].droga=1; 
					continue;
				}
				tmp = Console.readString("A["+ i + ", "+ j + "]");
				if (tmp.compareTo("niesk") != 0) {
					A[i][j].odl = Integer.parseInt(tmp);
					A[i][j].droga=1;
				}
				else {
					A[i][j].odl=0;
					A[i][j].droga=0;
				}
			}
		
		//algorytm Floyda
		for (k=0; k<n; k++)
			for (i=0; i<n; i++)
				for (j=0; j<n; j++) {
					if((A[i][k].droga==1)&&(A[k][j].droga==1)) {
						if (A[i][j].droga==0)
							A[i][j].odl=A[i][k].odl+A[k][j].odl; //jesli droga i,j nie istnieje to musi to byc suma drog i,k+k,j
						else
							A[i][j].odl=Math.min(A[i][j].odl, A[i][k].odl+A[k][j].odl); //jesli istnieje to wybierz minimum z drog i,j oraz i,k+k,j
						A[i][j].droga=1;
					}
				}
		
		//wypisanie wynikow
		for (i=0; i<n; i++)	{
			System.out.println("");
			for (j=0; j<n; j++)
				if (A[i][j].droga==0)
					System.out.print(" D["+i+", "+j+"]=niesk.  "); 
				else
					System.out.print(" D["+i+", "+j+"]=" + A[i][j].odl);
		} 		
	}
}