excursie

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.

  Timp maxim de executie/test: 0.5 secunde

Paul Diac
Universitarea « Al. I Cuza », Iasi – Facultatea de informatica
Contact:diac_paul@yahoo.com