/* **************************************************************
 *		RESENI PROBLEMU OBCHODNIHO CESTUJICIHO
 *
 ************************************************************** */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>


// DATA ------------------------------------------------------------
//nactena data ze souboru (zadani)
unsigned char *matice = NULL;	//matice souslednosti
int count = -1;								//pocet mest

//informace o aktualni ture
int *circle = NULL;		//posloupnost cisel mest na ture
int length;						//delka aktualni tury

//data pro sestavovani pocatecni kruznice
bool *added = NULL;		//pridani jednotlivych mest pri vytvareni kruznice
int cnt = 0;					//pocet mest na ceste pri vytvareni kruznice



// POMOCNE FUNKCE --------------------------------------------------
// alokace bool pole a naplneni zadanou hodnotou 
bool* BoolArray(int count, bool value)
{
	bool *res = new bool[count];
	for (int i = 0; i < count; i++)
		res[i] = value;
	return res;
}


// alokace int pole a naplneni zadanou hodnotou 
int* IntArray(int count, int value)
{
	int *res = new int[count];
	for (int i = 0; i < count; i++)
		res[i] = value;
	return res;
}

// nahodne cislo v rozsahu 0..max-1
int Random(int count)
{
	int res = rand() + 1;
	while (res < count * 2)
		res *= rand() + 1;
	return res % count;
}


// nahodne cislo mesta
int RandomCity()
{
	return Random(count);
}

// NACITANI DAT -----------------------------------------------------
// Nacteni matice souslednosti ze zadaneho souboru 
void LoadData(const char *filename)
{
	//otevreni souboru
	FILE *hndl = fopen(filename, "rt");
	if (hndl == NULL) {
		printf("Soubor neotevren!!!");
		return;
	}
	//zjisteni velikosti souboru
	fseek(hndl, 0, SEEK_END);
	long size = ftell(hndl);
	fseek(hndl, 0, SEEK_SET);	//seek zpet na zacatek
	//alokace matice
	if (matice != NULL)
		delete[] matice;
	matice = new unsigned char[size];
	if (matice == NULL) {
		printf("Nelze alokovat matici!!!");
		return;
	}
	//nacteni souboru
	const int length = 1024;			//velikost bufferu
	char *buf = new char[length + 2];	//pomocny buffer
	int line = -1;
	int col = 0;
	int pos = 0;
	int done = 0;
	do
	{
		//precteni bufferu
		done = fread((void*)buf, 1, length, hndl);
		for(int i = 0; i < done; i++)
		{
			char c = buf[i];
			//novy radek
			if(c == '\n') 
			{
				//ulozeni poctu mest z delky druheho radku (na prvnim kod zadani)
				if (line == 1)
					count = col;
				//odradkovani
				line++;
				col = 0;
			}
			//cteni dat
			else if (line >= 0)
			{
				//cislo ! 0 = zadna hrana
				if (c >= '0' && c <= '9') {
					matice[pos++] = c - '0';
					col++;
				}
				//pismeno - 10, B=11, ... Z=?
				else if (c >= 'A' && c <= 'Z') {
					matice[pos++] = c - 'A' + 10;
					col++;
				}
				//spatny znak
				else {
					printf("!!!Spatny znak v souboru: %c\n", c);
				}
			}
		} //for
	} while (done == length);
	//zavreni souboru
	fclose(hndl);
}


// iniciace dat pro metodu - alokace poli 
// volat az po nacteni dat - je treba znat pocet mest
void DataInit()
{
	//alokace pole pro ulozeni pnosti mest
	if (circle != NULL)
		delete[] circle;
	circle = IntArray(count, -1);
	//delka cesty
	length = 0;
}


// Zjisteni vzdalenosti mezi mesty 
int RoadLength(int cityA, int cityB)
{
	return (int)matice[cityA * count + cityB];
}


// SESTAVENI POCATECNI KRUZNICE -------------------------------------
//	prodlouzeni existujici cesty z daneho mesta koncoveho mesta
// false pokud nelze, nastavuje nove koncove
bool Prodluz(int &from)
{
	//test cesty do vsech neobsazenych mest
	for(int i = 0; i < count; i++)
	{
		int road;
		//? je i-te neopridane a jde from->i - nastav nove koncove
	  if ( (!added[i]) && ((road = RoadLength(from, i)) > 0) )
		{
			added[i] = true;
			circle[cnt++] = i;	//pridani do cesty
			length += road;			//prodlouzeni delky
			from = i;						//nove koncove
			return true;
		}
	}
	return false;
}


//	pokus o uzavreni kruznice z daneho mesta do pocatecniho
// neni testovana pridani vsech mest na ceste
bool Uzavri(int from)
{
	int road = RoadLength(from, circle[0]);
	//je cesta from->start
	if ( road > 0 )
	{
		length += road;
		return true;
	}
	return false;
}


//  modifikace cesty - prevedeni cesty z libovolneho nekoncoveho mesta (i)
//  do mesta koncoveho a "rozpojeni" mezi i a i+1; lze pouze pokud mesto i+1
//  neni zakazane - pokud bude jako koncove, nepomuzeme si
// nastavuje nove koncove mesto na i+1
bool Modifikuj(int &endCity, bool *forbidden)
{
	//test vsech mest na existujici ceste
	//ne posledni 2 - posledni je endCity, predposlednim by se posledni nezmenilo
	for (int i = 0; i < cnt - 2; i++)
	{
		int city = circle[i];
		int newEnd = circle[i+1];		//potencialni novy konec cesty
		int road;
		//? ma smysl prepojovat s koncovym newEnd a existuje cesta do soucasneho konce
		if ( (!forbidden[newEnd]) && ((road = RoadLength(city, endCity)) > 0) )
		{
			// prepojeni cesty -----
			int j;
			int* newCircle = IntArray(count, -1);
			//cesta do i - ponechame
			for (j = 0; j <= i; j++)
				newCircle[j] = circle[j];
			//cesta ze soucasneho konce do i+1 - prehozeni
			int pom = cnt + i;		//urychleni
			for (j = i+1; j < cnt; j++)
				newCircle[j] = circle[pom - j];
			//zmena poli cesty
			delete[] circle;
			circle = newCircle;
			//zmena delky - prictem nova-stara
			length += road - RoadLength(city, newEnd);
			// nove koncove -----
			endCity = newEnd;
			return true;
		}
	}
	return false;
}


//  nalezeni pocatecni Hamilt. kruznice
// false pokud kruznice neex
bool FindCircle()
{
	// priprava dat ---
	//pole pridanych
	if (added != NULL)
		delete[] added;
	added = BoolArray(count, false);
	//iniciace dat
	length = 0;				//delka kruznice
	cnt = 0;					//pocet mest v ceste
	int startCity = 0;//pocatek kruznice
	// pridani startcity ---
	added[startCity] = true;
	circle[cnt++] = startCity;
	// aktualni koncove mesto - pocatecni v kruznici ---
	int index = startCity;	
	//pole zakazanych - mesta bez cest do zadneho z dosud nepouzitych mest
	bool *forbidden = BoolArray(count, false);
	//cykly dokud nenaleznes kruznici pres vsechny mesta
	while (true)
	{
		//? nejsou jeste vsechna mesta na ceste
		if (cnt < count)
		{
			//? nelze prodlouzit
			if (! Prodluz(index) )		//pri zdarenem prodlouzeni se meni index mesto a zvetsuje cnt
			{
				//zakazeme ho
				forbidden[index] = true;
				//zkusime zamenit cestu
				if (! Modifikuj(index, forbidden) )		//meni index
					return false;
			}
		}
		//chyby jen spojeni koncovych mest
		else
		{
			//jine zakazove kriterium - nulujeme
			//zakazane je mesto, z nejz nevede cesta do pocatecniho mesta
			for(int i = 0; i < count; i++)
				forbidden[i] = false;
			//zkouseni 
			while(true)
			{
				//? lze uzavrit kruznici z tohoto konc. mesta
				if ( Uzavri(index) )
					return true;
				//nelze - zakazeme ho a zkusime predelat cestu
 				forbidden[index] = true;
				if (! Modifikuj(index, forbidden) )	//meni index
					return false;		//pokud nelze predelat, kruznice neex.
			}
		}	//else
	} // while(true)
	delete[] forbidden;
	delete[] added;
	added = NULL;
}


// METODY HLEDANI NOVEHO STAVU -------------------------------------------
// Vysledek volby noveho stavu
enum EChangeResult {
	BETTER,				//zlepseni
	THE_SAME,			//stejna delka
	WORSE,				//prijmute zhorseni
	NOT_ACCEPTED,	//neprijmute zhorseni
	NOT_FOUND			//zamena nenalezena
};

//  Akceptace novych stavu - povoli ci zakaze zmenu podle aktualni
//  teploty, testuje se rozdil old - new ... prodlouzeni puvodni cesty
bool AcceptChange(int change, double temper)
{
	//? zlepseni
	if (change < 0)
		return true;
	//? povolime pri dane teplote
	double test = (double)rand() / double(RAND_MAX);	//nahodne cislo <0,1>
	if ( test < exp(-(double)change / temper) )
		return true;
	//moc velke zhorseni
	return false;
}


//  Obecna dvouzamena - prekrizeni cest: i -> j ... i+1 -> j+1
//  Vraci prvni nalezenou zmenu schvalenou pomoci AcceptChange
// Nastavuje city1 na i, city2 na j, newLength na novou delku kruznice (nemeni kruznici!)
// vraci 0 pokud prohozeno, 1 pokud nic neschvaleno, 2 pokud nic nenalezeno
EChangeResult DoubleChange(double temper)
{
	int 
		a, b,					//nahodne zvolena mesta
		road1, road2;	//delky novych cest
	int maxCount = count*count;		//max pocet voleb
	int counter = 0;	//pocet voleb mest
	// vyber dvou mest vhodnych pro zamenu
	do
	{
		//? nic v zadanem poctu nenalezeno
		if (counter > maxCount)
			return NOT_FOUND;
		//vyber dve mesta
		a = RandomCity();
		b = RandomCity();
		//serad - a < b
		if (a > b) 
		{
			int pom = a;
			a = b;
			b = pom;
		}
		counter++;
		road1 = 0;	//zmena nejde
		//? ma smysl zmena - nutno mezi nimi alespon jedno mesto
		if (b >= a + 2)
		{
			//zjisti delky novych cest
			road1 = RoadLength(circle[a], circle[b]);
			road2 = RoadLength(circle[a + 1], circle[(b+1)%count]);
		}
	} while ( (road1 == 0) || (road2 == 0) );
	// zjisteni zmeny delky cesty
	int change = road1 + road2;		//delka nove
	change -=	RoadLength(circle[a], circle[a+1]) + RoadLength(circle[b], circle[(b+1)%count]);	//odecteni delky stare
	//? lze zmenit - predelani cesty
	if ( AcceptChange(change, temper) )
	{
		int *newCircle = IntArray(count, -1);
		int i;
		//kopirovany zacatek
		for (i = 0; i <= a; i++)
			newCircle[i] = circle[i];
		//prohozeny stred
		int pom = a + b + 1;
		for ( ; i <= b; i++)
			newCircle[i] = circle[pom - i];
		//kopirovany konec
		for ( ; i < count; i++)
			newCircle[i] = circle[i];
		//prohozeni poli
		delete[] circle;
		circle = newCircle;
		//zmena delky
		length += change;
		if (change > 0)
			return WORSE;
		if (change < 0)
			return BETTER;
		return THE_SAME;
	}
	return NOT_ACCEPTED;
}

// SAMOTNE OCHLAZOVANI --------------------------------------------------
// DATA -----
//nastaveni metody
double startTemper;	//pocatecni teplota
double coolCoef;		//koeficient ochlazovani
double minTemper;		//teplota zmrznuti
double maxIter;			//max. pocet iteraci pro jednu teplotu

//nejlepsi a nejhorsi vysledky
int minLength;
int maxLength;


// METODY -----
//uchovani nejlepsiho a nejhorsiho vysledku
void SaveExtremes(int length)
{
	if (length > maxLength)
		maxLength = length;
	else if (length < minLength)
		minLength = length;
}


// test ukonceni vnitrniho cyklu
// parametry: vysledek prohozeni, poctu vnitrnich iteraci a teploty
bool Equilibrium(EChangeResult res, int iterCount, double temper)
{
	return iterCount > maxIter;
}


int notTakenCount = 0;
// test "zmrazeni" - konec vnejsiho cyklu
// konec pokud v celem vnitrnim cyklu zadna zmena
bool Frozen(double temper, int iterCount, bool changed)
{
	return temper < minTemper;
}


// Snizeni teploty
double Cool(double temper, int iterCount)
{
	return temper * coolCoef;
}


// Hlavni cyklus metody simulovaneho ochlazovani
int DoOchlazovani()
{
	//iniciace
	double t = startTemper;	//aktualni teplota
	int iterCount = 0;			//celkovy pocet iteraci
	minLength = maxLength = length;	//nastaveni na delku pocatecniho reseni
	bool changed = false;		//flag prijmuti nejakeho stavu
	//postupne ochlazovani
	do
	{
		EChangeResult res;
		int innerIter = 0;		//vnitrni pocitadlo pro ukonceni cyklu
		changed = false;
		//zmeny pri zadane teplote
		do
		{
			//pokus o zmenu, vraci jestli zmena sla ci nesla provest
			res = DoubleChange(t);
			//? zmena - flag + ulozeni extremu
			if ((res == BETTER) || (res == WORSE))
			{
				changed = true;
				SaveExtremes(length);
			}
			//pocitadla
			innerIter++;	//vnitrni pocet
		} while(! Equilibrium(res, innerIter, t) );
		iterCount += innerIter;
		//ochlazeni
		t = Cool(t, iterCount);
	} while(! Frozen(t, iterCount, changed) );
	return iterCount;
}


// Spousteni metody simul. ochlazovani - nastavi poc data a spusti metodu
void Ochlazovani(double t0, double alfa, double frozen, int inner, FILE* output)
{
	//nastaveni metody
	startTemper = t0;
	coolCoef = alfa;
	minTemper = frozen;
	maxIter = inner;
	//spusteni metody
	int iter = DoOchlazovani();
	fprintf(output, "%8f %8f %8f %5d | %10d %10d\n", t0, alfa, frozen, inner, length, iter);
}


// testovani -------------------------------------------
// vypis vzdalenosti mezi mesty 
void TestRoad(int cityA, int cityB)
{
	printf("vzdalenost %d -> %d: %d\n", cityA, cityB, RoadLength(cityA, cityB));
}


// zkontrolovani vytvorene kruznice 
void TestCircle()
{
	bool *added = BoolArray(count, false);
	int testLength = 0;
	for (int i = 0; i < count; i++)
	{
		int city = circle[i];
		//kontrola aktualniho mesta
		if (added[city]) {
			printf("Mesto %d pridano podruhe (index %d z %d)\n", city, i, count);
		}
		added[city] = true;
		//kontrola cesty do dalsiho
		int nextCity = circle[(i+1) % count];
		int road = RoadLength(city, nextCity);
		if (road <= 0) {
			printf("Neexistuje cesta %d -> %d (index %d z %d)\n", city, nextCity, i, count);
		}
		testLength += road;
	}
	//kontrola delky
	if (length != testLength)
		printf("Nesouhlasi delka cesty - spocteno %d, uvedeno %d\n", testLength, length);
}

//zkopirovani dvou "kruznic" - posloupnosti cisel mest v poli
void CopyCircles(int *source, int *dest)
{
	for (int i = 0; i < count; i++)
		dest[i] = source[i];
}

//vystupni soubor
const char* OUTPUT_FILE = "output.out";

//postupne reseni problemu s ruznymi nastavenimi
void FindSolvations(const char *filename)
{
	//zalozni pole pro startovani
	int* backup = new int[count];
	CopyCircles(circle, backup);
	int oldLength = length;
	//otevreni vystupni souboru a hlavicka
	FILE *output = fopen(OUTPUT_FILE, "wo");
	fprintf(output, "%s\n", filename);
	fprintf(output, "Pocatecni reseni: %d\n", length);
	printf("\n");
	//startovaci teplota
	for (double t0 = 10.0; t0 <= 60.0; t0 += 10.0)
		//koeficient chlazeni
		for (double alfa = 0.6; alfa < 1; alfa += 0.05)
			//minimalni teplota
			for (double minT = 0.1; minT > 0.00001; minT *= 0.1)
				//pocet vnitrnich cyklu
				for (int inner = count; inner <= 2 * count; inner *= 2)
				{
					//proved cyklus
					Ochlazovani(t0, alfa, minT, inner, output);
					//obnov pocatecni data a delku
					CopyCircles(backup, circle);
					length = oldLength;
					//info uzivateli
					printf(".");
					fflush(stdout);
				}
	printf("\n");
	fclose(output);
}

// otestovani souboru
void TestFile(const char *filename)
{
	printf("Zpracovavane zadani: %s\n", filename);
	//nacteni dat
	LoadData(filename);
	printf("  Nacteno, pocet mest: %d\n", count);
	//iniciace vnitrnich struktur
	DataInit();	
	//hledani pocatecniho reseni
	bool found = FindCircle();
	if (found) 
	{
		printf("  Nalezena kruznice, delka: %d\n", length);
		//FindSolvations(filename);
		Ochlazovani(3, 0.8, 1.3, 100, stdout);
	}
	else
		printf("  Hamiltonovska kruznice neexistuje\n\n");
//	printf("%10s %10d %10d %10s\n", filename, count, length, (found) ? "OK" : "NOT FOUND");
}


/* testovaci fce */
void main()
{
	srand(time(NULL));
	//TestFile("data/test.txt");
	
	TestFile("data/A.txt");
	//TestFile("data/B.txt");
	//TestFile("data/D.txt");
	//TestFile("data/E.txt");
	//TestFile("data/J.txt");
	//TestFile("data/Testik.txt");
/*
	TestFile("data/C.txt");
	TestFile("data/F.txt");
	TestFile("data/G.txt");
	TestFile("data/H.txt");
	TestFile("data/I.txt");
	TestFile("data/K.txt");
	/**/
}


//////////////////////////////////////////////////////////////////
// VARIANTA s poli BEFORE a AFTER (seznamy) ---------------------
/*  Pridani silnice A->B do cesty
 *  nastavuje before a after mest, prodluzuje delku
 * vraci true pokud existuje cesta 
bool AddRoad(int cityA, int cityB)
{
	int road = RoadLength(cityA, cityB);
	//? existuje cesta
	if (road > 0)
	{
		after[cityA] = cityB;
		before[cityB] = cityA;
		length += road;
		return true;
	}
	return false;
}


// SESTAVENI POCATECNI KRUZNICE -------------------------------------
/*	prodlouzeni existujici cesty z daneho mesta koncoveho mesta
 * false pokud nelze, nastavuje nove koncove
bool Prodluz(int &from)
{
	//test cesty do vsech neobsazenych mest
	for(int i = 0; i < count; i++)
	{
		//? je i-te neopridane a jde from->i - nastav nove koncove
	 if (! added[i]) 
		if ( AddRoad(from, i) ) 
		{
			cnt++;
			added[i] = true;
			from = i;				
			return true;
		}
	}
	return false;
}

/*	pokus o uzavreni kruznice z daneho mesta do pocatecniho
 * neni testovana pridani vsech mest na ceste
bool Uzavri(int from)
{
	//je cesta from->start
	if ( AddRoad(from, startCity) )
		return true;
	return false;
}

/*  modifikace cesty - prevedeni cesty z libovolneho nekoncoveho mesta (i)
 *  do mesta koncoveho a "rozpojeni" mezi i a i+1; lze pouze pokud mesto i+1
 *  neni zakazane - pokud bude jako koncove, nepomuzeme si
 * nastavuje nove koncove mesto na i+1
bool Modifikuj(int &endCity, bool *forbidden)
{
	//test vsech mest na existujici ceste
	//ne posledni 2 - posledni je endCity, predposlednim by se posledni nezmenilo
	int city = startCity;		//akrualni misto
	for (int i = 0; i < cnt - 2; i++)
	{
		int newEnd = after[city];		//potencialni novy konec cesty
		//ma smysl prepojovat s koncovym newEnd a existuje cesta do soucasneho konce
	 if (! forbidden[newEnd] )
		if ( AddRoad(city, endCity) )
		{
			// prepojeni cesty -----
			int lastCity = -1;	//rozpojeni konce
			//prostredek
			for (int ct = newEnd; ct != endCity; ct = before[ct])
			{
				before[ct] = after[ct];
				after[ct] = lastCity;
				lastCity = ct;
			}
			//stare posledni mesto
			after[endCity] = lastCity;
			// odecteni delky odebrane silnice -----
			length -= RoadLength(city, newEnd);
			// nove koncove mesto cesty -----
			endCity = newEnd;
			return true;
		}
		city = newEnd;
	}
	return false;
}

/*  nalezeni pocatecni Hamilt. kruznice 
 * false pokud kruznice neex
bool FindCircle()
{
	//priprava dat ---
	//pole pridanych
	if (added != NULL)
		delete[] added;
	added = BoolArray(count, false);
	//pole zakazanych - mesta bez cest do zadneho z dosud nepouzitych mest
	bool *forbidden = BoolArray(count, false);
	//pocty
	length = 0;				//delka kruznice
	startCity = 0;		//pocatek kruznice
	added[startCity] = true;
	cnt = 1;					//pocet dosud zahrnutych mest - pocatecni
	//soucasne koncove mesto - pocatecni v kruznici
	int index = startCity;	
	//cykly dokud nenaleznes kruznici pres vsechny mesta
	while (true)
	{
		//? nejsou jeste vsechna mesta na ceste
		if (cnt < count)
		{
			//? nelze prodlouzit
			if (! Prodluz(index) )		//pri zdarenem prodlouzeni se meni index mesto a zvetsuje cnt
			{
				//zakazeme ho
				forbidden[index] = true;
				//zkusime zamenit cestu
				if (! Modifikuj(index, forbidden) )		//meni index
					return false;
			}
		}
		//chyby jen spojeni koncovych mest
		else
		{
			//jine zakazove kriterium - nulujeme
			//zakazane je mesto, z nejz nevede cesta do pocatecniho mesta
			for(int i = 0; i < count; i++)
				forbidden[i] = false;
			//zkouseni 
			while(true)
			{
				//? lze uzavrit kruznici z tohoto konc. mesta
				if ( Uzavri(index) )
					return true;
				//nelze - zakazeme ho a zkusime predelat cestu
 				forbidden[index] = true;
				if (! Modifikuj(index, forbidden) )	//meni index
					return false;		//pokud nelze predelat, kruznice neex.
			}
		}	//else
	} // while(true)
	delete[] forbidden;
	delete[] added;
	added = NULL;
}

//testovani -------------------------------------------
/* zkontrolovani vytvorene kruznice 
int* CreateCircle()
{
	int *circle = new int[count];
	bool *added = BoolArray(count, false);
	int testLength = 0;
	int city = startCity;
	for (int i = 0; i < count; i++)
	{
		circle[i] = city;
		//kontrola aktualniho mesta
		if (added[city]) {
			printf("Mesto %d pridano podruhe (index %d z %d)\n", city, i, count);
		}
		added[city] = true;
		//kontrola cesty do dalsiho
		int nextCity = after[city];
		int road = RoadLength(city, nextCity);
		if (road <= 0) {
			printf("Neexistuje cesta %d -> %d (index %d z %d)\n", city, nextCity, i, count);
		}
		testLength += road;
		//kontrola zpetneho propojeni
		if (before[nextCity] != city)
			printf("Spatna zpetny pointr u silnice %d -> %d (index %d z %d)\n", city, nextCity, i, count);
		//posun mesta
		city = nextCity;
	}
	//kontrola uzavreni a delky
	if (city != startCity)
		printf("Kruznice neni uzavrena\n");
	if (length != testLength)
		printf("Nesouhlasi delka cesty - spocteno %d, uvedeno %d\n", testLength, length);
	return circle;
}

// PROCHAZENI VSECH MEST ----------------------------------------------------------
	
//  Obecna dvouzamena - prekrizeni cest: i -> j ... i+1 -> j+1
//  Vraci prvni nalezenou zmenu schvalenou pomoci AcceptChange
// Nastavuje city1 na i, city2 na j, newLength na novou delku kruznice (nemeni kruznici!)
// vraci 0 pokud nalezne, 1 pokud nic neschvaleno, 2 pokud nic nenalezeno
int DoubleChange(int &city1, int &city2, int &newLength)
{
	bool found = false;
	//posledni dve jiz nejde z nasledniky krizit
	for (int i = 0; i < count - 2; i++)
	{
		//maximum - s prvnim mestem nelze krizit posledni
		int max = (i == 0) ? count - 1 : count;
		//testovani dvojic mest
		for (int j = i + 2; j < max; j++)
		{
			int road1 = RoadLength(circle[i], circle[j]);
			if (road1 > 0)
			{
				int road2 = RoadLength(circle[i+1], circle[j+1]);
				//? nalezena dvojice, ktera lze prohodit
				if (road2 > 0)
				{
					found = true;
					int road = road1 + road2;
					//delka rusenych cest
					int oldRoad = RoadLength(circle[i], circle[i+1]) + RoadLength(circle[j], circle[j+1]);
					//? lze provest zmenu cesty - nastaveni vysledku
					if ( AcceptChange(road - oldRoad) )
					{
						city1 = i;
						city2 = j;
						newLength = length - oldRoad + road;
						return 0;
					}
				} //if road2
			} //if road1
		} //for j
	} //for i
	//zadna zamena neakceptovana
	return (found) ? 1 : 2;
}

/**/