Costel este un impatimit
al calatoriilor. In vacanta a planuit o excursie in care sa strabata cat mai
multe judete din regiunea in care locuieste, Transilvania. In Transilvania localitatile
sunt organizate in 10 judete identificate prin cate doua litere: AB,
BN, BV, CJ, CV, HD, HR, MS, SB si SJ. Localitatile sunt identificate
in mod unic printr-un sir de 3 caractere. Primele doua sunt litere mari si reprezinta
judetul din care fac parte localitatile (unul dintre cele 10 posibilitati).
Al treilea caracter este o cifra ('0' - '9') ce face distinctia dintre localitati
din acelasi judet. Drumuri de diferite lungimi unesc in ambele directii perechi
de localitati.
In excursia sa, Costel doreste
sa viziteze cat mai multe judete. El este insa restrictionat de configuratia
drumurilor si chiar a localitatilor: pot exista localitati izolate si judete
izolate sau fara localitati. Determinati numarul maxim de judete pe care le
poate vizita Costel si lungimea minima a unui traseu ce face posibil acest lucru.
Totodata, traseul ales trebuie sa se intoarca in localitatea de pornire, unde
locuieste Costel.
Date
de intrare
Fisierul excursie.in contine pe prima linie identificatorul localitatii
in care locuieste Costel. Pe urmatoarele linii se afla configuratii ale drumurilor:
identificatori a doua localitati intre care exista drum si un numar intreg reprezentand
lungimea in kilometri a drumului, separate prin cate un spatiu. Exista doar
localitati de la care pleaca cel putin un drum, astfel localitatile sunt definite
de configuratia drumurilor.
Date
de iesire
Fisierul
excursie.out trebuie sa contina o singura linie pe care vor fi scrise
doua numere intregi, separate prin spatiu, reprezentand numarul de judete vizitate
de traseul optim si lungimea acestuia.
Restrictii
si precizari
Lungimea in kilometri
a oricarui drum este un numar intreg ce nu depaseste 10000.
Intre orice doua localitati
exista cel mult un drum direct.
Numarul maxim de localitati
este dat de numarul maxim de identificatoare distincte.
In fisierul de intrare
nu vor exista mai mult de 1000 drumuri directe.
Un traseu este o succesiune
de localitati nu neaparat distincte.
Lungimea unui traseu
este suma lungimii drumurilor parcurse de acesta.
Traseul
poate fi urmatorul: BV0-BV2-SB0-BV2-BV0-MS2-CV1-HR5-CV1-MS2-BV0
care:
Trece prin 5 judete: BV, SB, MS, CV, HG
Are lungimea 10+10+10+10+7+3+2+2+3+7
= 64
Nu exista alt traseu care sa treaca prin mai mult de 5 judete sau prin
5 judete dar sa aiba lungimea mai mica.
Paul
Diac Universitarea
« Al. I Cuza », Iasi – Facultatea de informatica