Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | ubuntzei.in, ubuntzei.out | Sursă | OJI 2011, clasele 11-12 |
| Autor | Marius Stroe | Adăugată de |  Petru Trimbitas •S7012MY |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Ubuntzei
Trei ubuntzei au hotărât ca anul acesta să petreacă ziua de 1 Mai pe malul Mării Negre împreună cu prietenii lor, motiv pentru care au pus la cale o excursie pe un traseu care să plece din oraşul lor Cluj-Napoca spre Vama Veche, unde nisipul îi aşteaptă.
În ţara ubuntzeilor există N localităţi, numerotate de la 1 la N, legate între ele prin M şosele bidirecţionale de diferite lungimi. Localitatea de plecare a ubuntzeilor, oraşul Cluj-Napoca, este numerotată cu 1, iar localitatea destinaţie, Vama Veche, cu N. Între oricare două localităţi există cel mult o şosea. Fiecare şosea uneşte două localităţi distincte şi se poate călători între oricare două localităţi circulând numai pe şosele.
Prietenii ubuntzeilor locuiesc în K localităţi distincte, diferite de Cluj-Napoca şi Vama Veche. Pentru a nu călători singuri, cei trei ubuntzei vor să treacă prin cele K localităţi în care locuiesc prietenii lor, şi apoi, împreună cu aceştia, să-şi continue excursia către mare.
Nerăbdători să ajungă cât mai repede la destinaţie, ubuntzeii s-au hotărât să îşi stabilească un traseu de lungime minimă care să treacă prin toate cele K localităţi.
Cerinţă
Scrieţi un program care să determine, pentru ubuntzei, lungimea minimă L a unui traseu de la Cluj-Napoca la Vama Veche ce trece prin toate cele K localităţi.
Date de intrare
Prima linie a fişierului de intrare ubuntzei.in conţine două numere naturale N M, separate printr-un spaţiu, cu semnificaţia din enunţ. A doua linie a fişierului conţine K+1 numere naturale distincte: K C1 C2 ... CK, separate prin câte un spaţiu, K având semnificaţia din enunţ iar C1,C2,... ,CK reprezentând cele K localităţi în care locuiesc prietenii. Fiecare din următoarele M linii conţine câte trei numere naturale x y z, separate prin câte un spaţiu, reprezentând o şosea care leagă localitatea x de localitatea y şi are lungimea z.
Date de ieşire
Fişierul de ieşire ubuntzei.out va conţine o singură linie pe care va fi scris numărul natural L reprezentând lungimea minimă căutată.
Restricţii
- 1 ≤ N ≤ 2 000
- 1 ≤ M ≤ 10 000
- 0 ≤ K ≤ min{15, N – 2}
- 2 ≤ C1,C2,... ,CK ≤ N-1
- Traseul poate trece de mai multe ori prin oricare localitate.
- Costul unei muchii va fi cuprins între 1 şi 105.
- Pentru primele 20% din teste K = 0.
- Pentru primele 50% din teste K ≤ 10.
- Pentru primele 70% din teste N ≤ 200.
Exemplu
| ubuntzei.in | ubuntzei.out |
|---|---|
| 4 5 1 2 1 2 1 1 3 1 2 3 1 2 4 4 3 4 2 | 4 |
Explicaţie
Există un singur traseu de lungime minimă de la localitatea 1 la localitatea 4 şi care trece prin localitatea 2, şi anume: [1,2,3,4]. Lungimea L a acestui traseu este 4.
