| Fişierul intrare/ieşire: | path2.in, path2.out | Sursă | preONI 2002 |
| Autor | Mugurel Ionut Andreica | Adăugată de |  Mugurel-Ionut Andreica •mugurelionut |
| Timp execuţie pe test | 0.025 sec | Limită de memorie | 5096 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Path2
Omul de afaceri Gigi trebuie sa ajunga in orasul J sa incheie un contract important. Inainte de a ajunge in orasul J pentru a incheia contractul, el trebuie sa treaca prin orasul I, unde are alta treaba importanta de rezolvat. Intrucat are un program foarte incarcat, Gigi vrea sa isi desfasoare intreaga calatorie intr-un timp cat mai scurt. De aceea, ar vrea sa stie lungimea minima a unui traseu care porneste din orasul in care se afla el initial (numerotat cu 1), trece prin orasul I si se termina in orasul J, cate astfel de trasee distincte (cu timp de parcurgere minim) exista si cateva dintre aceste trasee.
Date de intrare
In fisierul path2.in, pe prima linie, se afla 4 numere intregi: N M I J, reprezentand numarul de orase ale tarii in care se afla afaceristul Gigi, numarul de legaturi directe bidirectionale intre orase, numarul orasului in care trebuie sa ajunga Gigi mai intai si numarul orasului unde isi va termina Gigi calatoria. Pe fiecare din urmatoarele M linii se afla cate o pereche de orase intre care exista legatura directa.
Date de iesire
Pe prima linie a fisierului path2.out veti afisa T, reprezentand durata minima (in ore) a unui traseu care trece prin orasul I si se termina in orasul J. Pe a doua linie veti afisa numarul variantelor distincte de a ajunge in orasul J in timpul T (trecand prin orasul I). Pe urmatoarele linii veti afisa toate variantele (de lungime minima) de a ajunge in orasul J, trecand prin orasul I. Daca numarul acestor variante depaseste 100, atunci afisati doar 100 dintre ele (oricare 100). O varianta va fi afisata ca o succesiune de orase prin care trece Gigi: orasul de start (1) , orasul urmator, .. , I , .. , J, separate prin spatii. Intre oricare doua orase consecutive trebuie sa existe o legatura directa. Fiecare varianta va fi afisata pe o linie de una singura.
Restrictii
- 3 ≤ N ≤ 100
- 1 < I,J ≤ N
- I <> J
- 2 ≤ M ≤ N*(N-1)/2
- Timpul necesar parcurgerii unei legaturi directe intre 2 orase este 1 ora. Asadar, o varianta de lungime minima de a ajunge din orasul 1 in orasul J, trecand si prin orasul I este reprezentata printr-o succesiune de T+1 orase (unde T este timpul minim ce trebuie calculat)
- Numarul variantelor distincte de lungime minima va fi minim 1 si maxim 2 000 000 000
- Lui Gigi ii este permis sa treaca prin orasul J inainte de a ajunge in orasul I, dar el nu poate incheia contractul in orasul J decat dupa ce a trecut prin orasul I (asta inseamna ca ultimul oras al traseului sau trebuie sa fie obligatoriu orasul J)
Exemplu
| path2.in | path2.out |
|---|---|
| 7 8 7 4 1 2 1 3 2 4 3 4 4 5 4 6 5 7 6 7 | 6 8 1 2 4 5 7 5 4 1 2 4 5 7 6 4 1 2 4 6 7 5 4 1 2 4 6 7 6 4 1 3 4 5 7 5 4 1 3 4 5 7 6 4 1 3 4 6 7 5 4 1 3 4 6 7 6 4 |
