politie

Poliție

== include(page="template/taskheader" task_id="politie") ==

Poveste şi cerinţă...

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.
 
h2. 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ă.

h2. Date de intrare

Fişierul de intrare $politie.in$ ...

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$.
 

h2. Date de ieşire

În fişierul de ieşire $politie.out$ ...

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!

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N, D ≤ 250.000$
* $1 &le; P < N$
* $1 &le; M &le; 500.000$
* $1 &le; x,y &le; N$
* $x &ne; y$
* $1 &le; t &le; D$
* $1 &le; c &le; 1.000.000.000$
* nu pot exista mai multe străzi între două intersecţii $x$ şi $y$

h2. Exemplu

table(example). |_. politie.in |_. politie.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie

table(example). |_. politie.in |_. politie.out |_. Explicaţ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. |

...

== include(page="template/taskfooter" task_id="politie") ==