916 Trenuri

[•Marius]

Aici puteţi discuta despre problema Trenuri.

[•pauldb]

Am crescut limita de timp la 3.3 s pentru ca era foarte stransa. In plus, am adaugat in enunt o restrictie care lipsea.

[•bogdan2412]

Cred ca ar trebui adaugate id-urile problemelor in numele topicurilor la fel ca pentru celelalte probleme.

[•Marius]

Cred ca ar trebui adaugate id-urile problemelor in numele topicurilor la fel ca pentru celelalte probleme.

S-a rezolvat.

[•mathboy]

Nu inteleg ce as mai putea optimiza astfel incat sa iau 100 de puncte.

Fac ca in solutia oficiala, cu sortare, deque pt fiecare nod si programare dinamica pt fiecare muchie si cautarea binara din smenuri. Cei care au scos punctaj maxim, ce modificari ati adus ca sa scapati de TLE ?

[•Bogdan_tmm]

Ce nu ar fi bine in ideea asta:
Caut timpul binar(diferenta maxima minima dintre plecare si sosire) ,fac un dijkstra . Pentru fiecare nod pe care-l scot din coada(fie it o muchie care iese din nod)

daca trece de codul urmator relaxez muchia si sosire[it->y]=it->sosire;

Cod:

if(nod==1)
        sosire[nod]=it->plecare;
			
if(sosire[nod]>it->plecare)
	continue;
			
if(dif < it->plecare-sosire[nod])
	continue;
			
if(cost[it->y] <= cost[nod]+it->cost)
	continue;

Muchiile le retin exact cum se dau in fisierul de intrare.