1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include <iostream>
#include <string>

int BFS(bool** tablica, const uint16_t& n, uint16_t& start);

int main()
{
	std::string tmp;
	uint16_t n, k;
	uint16_t start = 0;
	uint16_t p1, p2;

	std::ios::sync_with_stdio(false);

	// Ilosc testow
	std::getline(std::cin, tmp);
	k = std::stoi(tmp);

	uint16_t* wyniki = new uint16_t[k];

	for (uint16_t test = 0; test < k; test++)
	{

		// Odczytanie i stworzenie grafu
		std::getline(std::cin, tmp);
		n = std::stoi(tmp);

		bool** autostrady = new bool* [n];

		for (uint16_t i = 0; i < n; i++)
		{
			autostrady[i] = new bool[n];
			std::getline(std::cin, tmp);
			// Macierz polaczen
			for (uint16_t j = 0; j < n; j++)
			{
				if (tmp[j] == '1')
					autostrady[i][j] = true;
				else
					autostrady[i][j] = false;
			}
		}

		// Test
		//std::cout << BFS(autostrady, n, start) << std::endl;
		//std::cout << "ostatnie: " << start << std::endl;

		// 1. BFS - znalezienie najdalszego punktu
		BFS(autostrady, n, start);
		p1 = start;

		// 2. BFS - znalezienie najdluzszej drogi
		BFS(autostrady, n, start);
		p2 = start;

		// Polaczenie najdalszych punktow w jeden (postawienie teleportu)
		for (int j = 0; j < n; j++)
		{
			autostrady[p1][j] += autostrady[p2][j];
			autostrady[j][p1] += autostrady[j][p2];
			autostrady[p2][j] = 0;
			autostrady[j][p2] = 0;
		}
		n--;

		// 3. i 4. BFS do znalezienia potrzebnej ilosci paliwa
		wyniki[test] = BFS(autostrady, n, p1);

		for (int j = 0; j < n + 1; j++)
		{
			delete[] autostrady[j];
		}
		delete[] autostrady;
	}

	for (uint16_t test = 0; test < k; test++)
	{
		std::cout << wyniki[test] << "\n";
	}

	std::cout << std::flush;

	delete[] wyniki;

	return 0;
}

int BFS(bool** tablica, const uint16_t &n, uint16_t &start)
{
	int16_t* kolejka = new int16_t[n];
	bool* odwiedzone = new bool[n];

	//int16_t i = 0;
	int16_t kIdx = 0;

	uint16_t aktualny = 0;
	uint16_t odleglosc = 0;
	uint16_t iloscStopien = 1;
	uint16_t iloscNastStopien = 0;

	for (int j = 0; j < n; j++)
	{
		kolejka[j] = -1;
		odwiedzone[j] = 0;
	}

	kolejka[kIdx] = start;

	while (kIdx < n)
	{
		// Kolejny element z kolejki

		aktualny = kolejka[kIdx];
		odwiedzone[kolejka[kIdx]] = 1;
		kIdx++;
		iloscStopien--;

		//std::cout << aktualny << " ";

		for (int j = 0; j < n; j++)
		{
			if (tablica[aktualny][j] == false)
				continue;
			if (odwiedzone[j] == 1)
				continue;
			// Dodanie nowego elementu do kolejki
			kolejka[kIdx + iloscStopien + iloscNastStopien] = j;
			iloscNastStopien++;
		}

		if (iloscStopien == 0)
		{
			iloscStopien = iloscNastStopien;
			iloscNastStopien = 0;
			odleglosc++;
		}

		if (iloscStopien == n - kIdx)
		{
			aktualny = kolejka[n - 1];
			break;
		}
	}

	//std::cout << std::endl << std::flush;
	start = aktualny;

	delete[] kolejka;
	delete[] odwiedzone;

	return odleglosc;
}