Fişierul intrare/ieşire:ubuntzei.in, ubuntzei.outSursăOJI 2011, clasele 11-12
AutorMarius StroeAdăugată deS7012MYPetru Trimbitas S7012MY
Timp execuţie pe test0.15 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/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.inubuntzei.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content