Rezolvare PBinfo #1069

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 numărul natural L reprezentând lungimea minimă căutată.

Restricții și precizări

• 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

4 5 
1 2
1 2 1
1 3 1
2 3 1
2 4 4
3 4 2

ubuntzei.out

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.