Clasa a X-a
Ziua 2
Problema 6

Problema de orientare turistica

La un concurs de orientare turistica organizatorii stabilesc traseele astfel īncat din punctul de start se poate ajunge in punctul de sosire pe mai multe poteci. Ajutati-i sa determine numarul traseelor care pot fi parcurse īn timpul minim posibil.

Date de intrare:
In fisierul de intrare TURIST.IN datele sunt scrise īn felul urmator:
- pe prima linie este scris un numar natural n (2<=n<=100), reprezentand numarul punctelor amenajate cu indicatoare;
- pe a doua linie sunt scrise doua numere naturale, reprezentānd numerele de ordine ale punctelor de start, respectiv de sosire;
- pe urmatoarele linii sunt scrise cāte trei numere naturale:
a b t
unde:
- a reprezinta numarul de ordine al unui punct amenajat cu indicator (1<=a<=n);
- b reprezinta numarul de ordine al punctului la care se poate ajunge direct (fara sa se intalneasca alte puncte de indicatoare) din a (1<=b<=n);
- t reprezinta timpul necesar pentru a parcurge distanta de la punctul a la punctul b (1<=t<=100).

Date de iesire:
In fisierul de iesire TURIST.OUT se vor scrie doua numere naturale. Primul numar reprezinta timpul minim necesar parcurgerii traseului dintre punctul de start si punctul de sosire, iar al doilea numar reprezinta numarul traseelor diferite care pot fi parcurse in acest timp minim. Doua trasee sunt identice daca au acelasi nu-mar de puncte cu indicatoare, intalnite in aceeasi ordine. Daca doua trasee nu sunt identice, ele sunt diferite.
Observatie:
Datele de intrare sunt corecte, nu necesita validare. Īntotdeauna se poate ajunge din punctul de start īn punctul de sosire.

Exemplu:
TURIST.IN
5
1 5
1 2 3
1 4 2
2 3 1
4 3 2
3 5 3

TURIST.OUT
7 2

Timp maxim de executare/test: 2 secunde
Punctaj maxim posibil: 50 puncte