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.
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.
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 C_1 C_2 ... C_K\), separate prin câte un spaţiu, K
având semnificaţia din enunţ iar \(C_1,C_2,... ,C_K\) 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
.
Fişierul de ieşire ubuntzei.out
va conţine numărul natural L
reprezentând lungimea minimă căutată.
1 ≤ N ≤ 2 000
1 ≤ M ≤ 10 000
0 ≤ K ≤ min{15, N – 2}
1
şi 105
.20%
din teste K = 0
.50%
din teste K ≤ 10
.70%
din teste N ≤ 200
.ubuntzei.in
4 5
1 2
1 2 1
1 3 1
2 3 1
2 4 4
3 4 2
ubuntzei.out
4
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
.
ID: 40
Upload: liviu
Input: ubuntzei.in/ubuntzei.out
Memory limit: 32MB/20MB
Time limit: 0.3s
Author: Marius Stroe
Source: OJI 2011 XI-XII: Problema 2