Fişierul intrare/ieşire:politie.in, politie.outSursăACM ICPC - Romanian Programming Contest 2016
AutorAndrei ParvuAdăugată deneapuiuComisie ICPC UPB neapuiu
Timp execuţie pe test1.2 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Politie

Nea Puiu, mafiot notoriu al Bucureştiului, este căutat de poliţie! Harta Bucureştiului este formată din N intersecţii legate prin M străzi bidirecţionale. Fiecare stradă are asociate două valori: un grad de periculozitate şi o categorie de drum în care se încadrează. În Bucureşti există D categorii de drumuri: categoria 1 este cea mai bună, apoi urmează categoria 2, ş.a.m.d.
Orice patrulă de poliţie care se deplasează dintr-o intersecţie x într-o intersecţie y va folosi străzi cât mai bune

  • dacă exista un drum între x şi y format numai din străzi de categoria 1, îl vor urma pe acela, indiferent de periculozitatea străzilor
  • în caz contrar, vor folosi un drum format din străzi din categoriile 1 sau 2;
  • dacă nu există niciun astfel de drum, vor folosi un drum format din străzi din categoriile 1, 2 sau 3;
  • şi aşa mai departe, acceptând în ultimă instanţă să folosească şi drumuri care conţin străzi din ultima categorie, D.

Bineînţeles, dintre toate drumurile posibile între două intersecţii, drumuri care respectă regulile de mai sus, poliţia îl va alege pe cel care are gradul maxim de periculozitate al străzilor folosite cât mai mic.
Deoarece nu se cunosc dinainte intersecţiile de plecare şi de sosire, poliţia trebuie să se gândească la toate variantele optime de patrulare dintre oricare două intersecţii.

Cerinţă

Cunoscand N, numărul de intersecţii, M, numărul de străzi, D numărul de categorii de drum posibile şi modul in care sunt conectate intersecţiile, determinaţi, dintre traseele optime de patrulare dintre oricare două intersecţii, cele mai mari P grade de periculozitate distincte prin care poliţia va trebui să treacă.

Date de intrare

Pe prima linie a fişierului politie.in se află 4 numere naturale N, M, D şi P, cu semnificaţia din enunţ. Urmează M linii, fiecare descriind o stradă a oraşului. A i-a dintre aceste linii descrie a i-a strada şi este formata din 4 numere: x, y, t şi c, reprezentând faptul ca există o stradă între intersecţiile x şi y, care aparţine categoriei t şi are gradul de periculozitate c.

Date de ieşire

Fişierul politie.out trebuie să conţina P linii: cele mai mari P grade de periculozitate sortate descrescător.
Atenţie! Cele P grade de periculozitate trebuie să fie distincte! Cu alte cuvinte, dacă există mai multe drumuri care conţin o stradă cu un grad y de periculozitate, acesta trebuie afişat doar o data!

Restricţii

  • 1 ≤ N, D ≤ 250.000
  • 1 ≤ P < N
  • 1 ≤ M ≤ 500.000
  • 1 ≤ x,y ≤ N
  • x ≠ y
  • 1 ≤ t ≤ D
  • 1 ≤ c ≤ 1.000.000.000
  • nu pot exista mai multe străzi între două intersecţii x şi y

Exemplu

politie.inpolitie.outExplicaţie
5 5 2 3
1 5 2 1
1 2 1 3
2 3 1 4
2 4 2 1
4 3 1 2
4
3
2
Muchiile dintre (2, 3), (1, 2) şi (3, 4) trebuie parcurse şi formează cele mai mari 3 costuri.
5 5 3 3
1 5 3 5
5 2 1 7
5 4 1 7
4 3 2 4
2 3 2 3
7
5
3
Muchiile dintre (5, 4), (5, 2) şi (1, 5) trebuie parcurse şi formează cele mai mari 3 costuri.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?