Prihlásenie Registrácia  

E - Diaľnice

Časový limit: 5s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Diaľnice sú odvekým problémom našej domoviny. Niektoré sú síce už postavené, ale mnoho ich ešte chýba. Odborníci vypracovali plán výstavby diaľníc a pre každú z nich odhadli jej cenu. Vláda však samozrejme nemá dostatok finančných prostriedkov, aby vybudovala všetky naplánované diaľnice. Preto sa rozhodla, že za daný rozpočet vybuduje tie diaľnice, ktoré s Bratislavou spoja čo najväčší počet miest.

Úloha

Daný je počet miest N, počet už postavených diaľníc M, počet naplánovaných diaľníc K a rozpočet na diaľnice R (v miliardách Sk). Pre každú postavenú diaľnicu je daná dvojica miest, ktoré diaľnica spája. Pre každú naplánovanú diaľnicu je daná dvojica miest, ktoré by diaľnica spojila a odhadovaná cena jej postavenia (v miliardách Sk).

Úlohou je nájsť takú množinu naplánovaných diaľníc, že ich celková cena neprekročí R a po ich postavení sa bude dať z Bratislavy (pomocou pôvodných a nových diaľníc) dostať do najväčšieho možného počtu ostatných miest.

Vstup

Prvý riadok vstupu obsahuje 4 celé čísla oddelené medzerou: N, M, K a R (1≤N≤15, 0≤M≤105, 0≤K≤105, 1≤R≤10000). Mestá sú pre jednoduchosť očíslované číslami od 1 po N, pričom Bratislava má číslo 1.

Nasleduje M riadkov popisujúcich postavené diaľnice. Každý z nich obsahuje dve rôzne medzerou oddelené čísla miest, ktoré diaľnica spája. Môžete predpokladať, že medzi dvoma mestami vedie nanajvýš jedna diaľnica.

Ďalších K riadkov popisuje naplánované diaľnice. Každý z nich obsahuje tri medzerou oddelené čísla: (rôzne) čísla miest, ktoré by diaľnica spojila a jej odhadovaná cena (celé kladné číslo neprekračujúce 1000). Môžete predpokladať, že medzi dvoma mestami je naplánovaná nanajvýš jedna diaľnica. Navyše, diaľnice sú naplánované len medzi mestami, medzi ktorými ešte diaľnica nevedie.

Výstup

Výstup by mal obsahovať na prvom riadku jediné číslo: maximálny počet miest, do ktorých sa bude z Bratislavy dať dostať pomocou pôvodných a novopostavených diaľníc. Druhý riadok by mal obsahovať počet novopostavených diaľníc. Ďalšie riadky by mali obsahovať medzerou oddelené čísla miest, medzi ktorými by sa mala naplánovaná diaľnica postaviť. Ak existuje viac správnych riešení, výstup by mal obsahovať ľubovoľné jedno z nich.

Príklad

Vstup

5 2 3 25
2 4
2 5
1 2 20
1 3 10
4 5 5

Výstup

3
1
1 2

Vysvetlenie

Postavením diaľnice medzi mestami 1 a 2 sa z mesta 1 (Bratislavy) bude dať dostať pomocou diaľníc do miest 2, 4 a 5. Na diaľnicu medzi mestami 1 a 3 už nebudú peniaze (spolu by tieto 2 diaľnice stáli 30 miliárd, čo je viac ako rozpočet), preto je 3 najlepší výsledok. Všimnite si, že diaľnicu medzi mestami 4 a 5 nemá zmysel stavať, lebo medzi týmito mestami sa diaľnicou už dá dostať (cez mesto 2).