| Fişierul intrare/ieşire: | atac2.in, atac2.out | Sursă | ONI 2008, clasele 11-12 |
| Autor | Alin Burta | Adăugată de |  Sima Cotizo •sima_cotizo |
| Timp execuţie pe test | 0.3 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Atac2
Costel, mare pasionat de jocuri de strategie, a descoperit de curand un joc nou. Acesta se joaca pe o harta compusa din n orase, numerotate de la 1 la n, unele dintre acestea fiind conectate prin drumuri directe. Este posibila deplasarea intre oricare doua orase utilizand drumurile existente. Costel a ajuns inaintea bataliei finale, cand adversarul sau mai stapaneste un singur oras. Notam acest oras cu x. Costel dispune de u unitati de armata, fiecare fiind cantonata intr-un oras oarecare, diferit de orasul x. Pentru a castiga, Costel trebuie sa deplaseze cate o unitate de armata in fiecare dintre orasele invecinate cu orasul x. Victoria nu este deloc sigura in situatia in care timpul total necesar transportului unitatilor nu este minim. Datorita tehnologiei avansate, drumul direct dintre oricare doua orase poate fi parcurs in timp constant egal cu o unitate de timp.
Scrieti un program care sa determine timpul total minim de deplasare a tuturor unitatilor necesare in orasele invecinate cu orasul x.
Date de intrare
Fisierul de intrare atac2.in contine:
- pe prima linie, 4 numere naturale n, m, u, x, separate prin cate un spatiu, n reprezentand numarul oraselor, m reprezentand numarul drumurilor directe existente intre orase, u reprezentand numarul unitatilor de armata de care dispune Costel, x reprezentand orasul in care se afla armata adversarului.
- pe a doua linie, u numere naturale, separate prin cate un spatiu, reprezentand orasele in care se afla cantonate cele u unitati de armata.
- fiecare din urmatoarele m linii contine cate doua numere naturale a si b, separate printr-un spatiu, cu semnificatia ca orasele a si b sunt legate printr-un drum direct.
Date de iesire
In fisierul de iesire atac2.out contine un singur numar natural reprezentand timpul total minim cerut.
Restrictii
- 1 < n ≤ 10 000
- 1 < m ≤ 100 000
- 0 < u ≤ 70
- Numarul oraselor invecinate cu x este cel mult egal cu numarul unitatilor de armata.
- Pe un drum se poate circula in ambele sensuri.
- Pentru 60% din teste u ≤ 8
Exemplu
| atac2.in | atac2.out |
|---|---|
| 7 11 3 7 6 1 3 1 4 2 5 3 1 3 5 4 5 5 1 6 2 6 3 6 4 7 4 7 5 | 2 |
Explicatie
Orasul 7 se invecineaza cu orasele 4 si 5, deci va fi nevoie sa deplasam doar 2 unitati dintre cele 3 disponibile.
Timpul minim necesar este 2. Exista mai multe variante pentru mutarea unitatilor, de exemplu:
- mutam unitatea din orasul 6 in orasul 4 (1 unitate de timp) si cea din orasul 3 in orasul 5 (1 unitate de timp)
- mutam unitatea din orasul 1 in orasul 4 (1 unitate de timp) si cea din orasul 3 in orasul 5 (1 unitate de timp)
