Fişierul intrare/ieşire:atac2.in, atac2.outSursăONI 2008, clasele 11-12
AutorAlin BurtaAdăugată desima_cotizoSima Cotizo sima_cotizo
Timp execuţie pe test0.6 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.inatac2.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)
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content