/* Problema comis-voiajorului
 */

package greedy;

import java.util.*;
import java.io.*;

public class ComisVoiajor
{
	private int valori[][],       // Distantele dintre sedii
				solutie[][],      // Vectorul solutie
				cost,
				nrSedii;          // Numarul de sedii

	public ComisVoiajor()
	{
		nrSedii = 0;
	}

	public int getNrSedii()
	{
		return nrSedii;
	}

	public void citireFisier(String numeFisier)
	{
		BufferedReader bf;
		StringTokenizer st;
		String linie;
		boolean linia1 = true;

		try
		{
			bf = new BufferedReader(new FileReader(numeFisier));

			while((linie = bf.readLine()) != null)
			{
				st = new StringTokenizer(linie, " \r\n\t");

				if(linia1)
				{
					nrSedii = Integer.parseInt(st.nextToken());

					valori = new int[nrSedii][nrSedii];
					solutie = new int[nrSedii][nrSedii];

					// Se initializeaza cu 0 matricea cu distante. Va fi drum intre
					// doua sedii i si j daca valori[i][j] = valori[j][i] != 0
					for(int i = 0; i < nrSedii; i++)
						for(int j = 0; j < nrSedii; j++)
							valori[i][j] = solutie[i][j] = 0;

					linia1 = false;
					continue;
				}
				else
				{
					int i, j;

					// S-a citit o linie care incepe cu un sediu i urmat de sediile j
					// care sunt legate de sediul i. Dupa fiecare sediu j urmeaza distanta
					// de la i la j
     				i = Integer.parseInt(st.nextToken());
					while(st.hasMoreTokens())
					{
      					j = Integer.parseInt(st.nextToken());
						valori[i][j] = valori[j][i] = Integer.parseInt(st.nextToken());
					}
				}
			}
		}catch(FileNotFoundException f)
				{
					System.out.println("Eroare la deschiderea fisierului " + numeFisier + ".");
				}
		 catch(IOException e)
		 		{
					System.out.println("Eroare de I/E.");
				}
	}

	public void greedy()
	{
  		int i, j, k, p, ni, minim, drum[][];

  		drum = new int[nrSedii][nrSedii];
		for(i = 0; i < nrSedii; i++)
			for(j = 0; j < nrSedii; j++)
				drum[i][j] = 0;

  		ni = 0;
  		drum[ni][ni] = cost = i = p = 0;

  		for(k = 0; k < nrSedii - 1; k++)
  		{
  			minim = 32767;
  			for(j = 0; j < nrSedii; j++)
  				if((valori[i][j] < minim) && (drum[i][j] == 0) && (valori[i][j] != 0))
  				{
					minim = valori[i][j];
					p = j;
				}
			solutie[i][p] = valori[i][p];
			cost += valori[i][p];
			drum[i][p] = drum[p][i] = 1;
			i = p;
		}

		cost += valori[p][ni];
		solutie[p][ni] = valori[p][ni];
	}

	public String toString()
	{
		String sir = "Drumul ales:\n";

		for(int i = 0; i < nrSedii; i++)
			for(int j = 0; j < nrSedii; j++)
				if(solutie[i][j] != 0)
					sir += "(" + (i+1) + ", " + (j+1) + ") = " + solutie[i][j] + "\n";
		sir += "Distanta parcursa: " + cost;

		return sir;
	}
}