Imperiul Hardland se află în război cu Niceland. Chiar dacă Niceland este o ţară mică, datorită rezistenţei eroice a locuitorilor, şi-a păstrat încă independenţa.
Spionii Hardland-ului însă au reuşit să obţină o hartă militară foarte importantă care conţine informaţii amănunţite atât despre oraşe, unităţi militare, depozite de muniţii şi armament, etc. pe care le vom numi puncte strategice. cât şi despre întreaga reţea de circulaţie din Niceland formată din căi de acces dintre două puncte strategice pe care le vom numi drumuri.
Cu ajutorul hărţii se pot localiza toate punctele strategice vulnerabile ale ţării, care se pot ocupa fără eforturi, cu ajutorul aviaţiei şi a unităţilor de paraşutişti. Aceste puncte strategice le vom numi baze militare iniţiale.
Din datele de pe hartă se pot calcula câţi rugu (unitatea monetară a ţării) ar costa ocuparea unui alt punct strategic încă neocupat, dacă luptele ar porni din punctele strategice vecine deja ocupate. De asemenea se ştie, că dacă două puncte strategice sunt deja ocupate de armata Hardland-ului, atunci folosirea drumului care leagă cele două localităţi nu va costa nimic.
Regele Hardland-ului doreşte să organizeze o acţiune militară completă pentru cucerirea întregului teritoriu al Niceland-ului cu cheltuieli minime.
Numărul punctelor strategice este n şi ele sunt numerotate cu 1, 2, ..., n.
Se cunosc pentru fiecare drum cheltuielile necesare cuceririi unui punct strategic neocupat dintr-un punct strategic apropiat deja cucerit. De asemenea se cunosc şi numerele de ordine a acelor localităţi care pot fi ocupate cu uşurinţă de aviaţie pentru a crea bazele militare iniţiale.
figura 1.
În figura 1 bazele militare iniţiale sunt în punctele strategice 2 şi 5. Conform hărţii din imagine, cucerirea întregii ţări va costa 29000 de rugu (drumuri ocupate: (2,3);(3,4);(2,1), cheltuieli: 14000+14000+1000=29000).
figura 2.
În figura 2 bazele militare iniţiale sunt în punctele strategice 2 şi 4. Conform hărţii din imagine, cucerirea întregii ţări nu se poate realiza.
Cerinţă
Scrieţi un program care să determine costul minim cu care se poate ocupa întreg teritoriul Niceland.Date de intrare
Fişierul de intrare war.in conţine pe prima linie trei numere naturale n, p şi k separate prin spaţiu, cu următoarele semnificaţii:n-numărul de puncte strategice, p-numărul de drumuri, k-numărul de baze militare iniţiale. Următoarele p linii conţin câte un triplet x y z separate prin spaţiu, cu semnificaţia că drumul dintre x şi y costă z rugu atunci când unul dintre punctele strategice x sau y este ocupat iar celălalt nu. Ultima linie conţine k numere naturale separate prin spaţiu u1, u2, ... , uk şi reprezintă punctele strategice ce formează bazele militare iniţiale.
Date de ieşire
Fişierul de ieşire war.out va conţine pe prima linie un singur număr: costul minim cu care se poate ocupa întreg teritoriul Niceland sau -1 dacă această cerinţă nu se poate realiza.Restricţii
- 2 <= n <= 1000
- Costul fiecărui drum este multiplu de 1000 si niciun cost nu depaseste 250000.
Exemple
| war.in | war.out | war.in | war.out |
5 6 2 |
29000 | 5 2 2 |
-1 |
| prof. Szabó Zoltan |
| Grupul Şcolar „Petru Maior” Reghin |
| szabozoliposta@yahoo.com |