54952023-07-01 16:58:23AndrosVillanyautócpp11Hibás válasz 34/6026ms6836 KiB
#include<algorithm>
#include <iostream>
#define maxN 301
#define Infi 10000000000



int varosszam, utszam, max_toltes;
long long T[maxN][maxN];
long long akku_graf[maxN][maxN];
long long T2[maxN][maxN];
long long X[maxN][maxN];


using namespace std;

void debug(long long A[maxN][maxN]) {
	for (int i = 1; i <= varosszam; i++)
	{
		for (int j = i + 1; j <= varosszam; j++)
		{
			//if (A[j][i] != A[i][j])cout << "SZIMETRIAVESZTESEG";
			cout << i << ", " << j << "\t" << A[i][j];
			cout << endl;
		}
	}
}

//Bekér két gráfot
//A-t módosítja
//					töltés					T2
void Szor(long long A[maxN][maxN], long long B[maxN][maxN]) {
	//X egy új gráf lesz
	for (int i = 1; i <= varosszam; i++)
		for (int j = 1; j <= varosszam; j++) {
			//Minden párra
			X[i][j] = Infi;

			for (int u = 1; u <= varosszam; u++)
				X[i][j] = min(X[i][j], max(A[i][u], B[u][j]));
		}

	//Átírja A-t X értékeire
	for (int i = 1; i <= varosszam; i++)
		for (int j = 1; j <= varosszam; j++)
			A[i][j] = X[i][j];
}

int main() {
	//Cin tie null
	int kezdo, veg;
	long long a = 0, b, hossz;
	cin >> varosszam >> utszam >> max_toltes;

	//Felvesz valami gráfot.
	//Minden éle végtelen, kivéve ha önmagába visz
	//Akkor 0
	//1-tõl indexel!
	for (int i = 1; i <= varosszam; i++) {
		T[i][i] = 0;
		for (int j = i + 1; j <= varosszam; j++) {
			T[j][i] = Infi;
			T[i][j] = Infi;
		}
	}

	//Az elõzõleg felvett gráfnál beállítja az élek hosszát
	for (int i = 0; i < utszam; i++) {
		cin >> kezdo >> veg >> hossz;
		T[kezdo][veg] = hossz;
		T[veg][kezdo] = hossz;
	}

	//cout << "Sima beolvasas";
	//debug(T);
	//cout << endl << endl;


	//Máténak igaza volt valszeg, ez minimális utat keres
	//Minden élre megnézi, hogy lehet-e javítani egy köztes node-al
	for (int koztes_node = 1; koztes_node <= varosszam; koztes_node++)
		for (int i = 1; i <= varosszam; i++)
			for (int j = 1; j <= varosszam; j++)
				//Minden számhármason. Ez nagyon lassúnak tûnik
				T[i][j] = min(T[i][j], T[i][koztes_node] + T[koztes_node][j]);

	//debug(T);

	//T2 másolata T-nek
	for (int i = 1; i <= varosszam; i++) {
		//Önmagába 0
		akku_graf[i][i] = 0;
		T2[i][i] = 0;

		for (int j = i + 1; j <= varosszam; j++) {
			T2[i][j] = T[i][j];
			T2[j][i] = T[i][j];
			//Átmásolja a T-t
			akku_graf[i][j] = Infi;
			akku_graf[j][i] = Infi;
			//E-t meg felveszi végtelen élekkel
		}
	}

	while (max_toltes > 0) {

		//if (max_toltes % 2 == 1) {
		//	Szor(akku_graf, T2);
		//}

		if (max_toltes == 1) {
			Szor(akku_graf, T2);
		}


		Szor(T2, T2);

		max_toltes /= 2;
	}

	//Maximális szükséges kapacitás kiválasztása
	for (int i = 1; i <= varosszam; i++)
		for (int j = i + 1; j <= varosszam; j++)
			a = max(a, akku_graf[i][j]);

	cout << a << "\n";
	return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base34/60
1Elfogadva0/03ms2052 KiB
2Elfogadva0/012ms3648 KiB
3Elfogadva1/14ms3412 KiB
4Elfogadva1/14ms3632 KiB
5Elfogadva1/14ms3744 KiB
6Elfogadva2/214ms4900 KiB
7Elfogadva2/212ms4816 KiB
8Elfogadva2/213ms5100 KiB
9Hibás válasz0/14ms4388 KiB
10Hibás válasz0/14ms4672 KiB
11Elfogadva1/14ms4572 KiB
12Hibás válasz0/217ms5456 KiB
13Hibás válasz0/224ms5628 KiB
14Hibás válasz0/219ms5928 KiB
15Elfogadva3/318ms6148 KiB
16Hibás válasz0/317ms6004 KiB
17Hibás válasz0/24ms5320 KiB
18Hibás válasz0/24ms5188 KiB
19Hibás válasz0/26ms5188 KiB
20Elfogadva2/26ms5328 KiB
21Elfogadva2/24ms5300 KiB
22Elfogadva2/24ms5500 KiB
23Hibás válasz0/323ms6704 KiB
24Elfogadva3/325ms6752 KiB
25Hibás válasz0/326ms6796 KiB
26Hibás válasz0/326ms6724 KiB
27Elfogadva3/317ms6500 KiB
28Elfogadva3/325ms6836 KiB
29Elfogadva3/318ms6752 KiB
30Elfogadva3/320ms6744 KiB