Clasa a XII-a
Ziua 2
Problema 3

Drum cat mai lung

Doi indragostiti se afla intr-un oras k si au la dispozitie p ore (p<=150), timp in care sa se plimbe cu masina si apoi sa ajunga fiecare la destinatie, fata in orasul i iar baiatul in orasul j. Ei doresc sa se plimbe cat mai mult timp impreuna dar sa ajunga in maxim p ore, fiecare in orasul sau
. Deplasarea cu masina pe sosele se face cu viteza constanta.
Ei au o dispozitie o harta cu n orase (3<=n<=200) intre care se afla orasul de plecare k si orasele destinatie i si j.
Harta indica modul in care sunt conectate orasele si durata exprimata in ore, a parcurgerii fiecarei sosele.
Sa se determine traseul pe care il vor parcurge cei doi indragostiti, astfel incat timpul petrecut impreuna sa fie maxim si sa ajunga amandoi la propria destinatie in cel mult p ore de la plecare.
Observatii:
- Cronometrarea duratei drumului se face incepand cu momentul 0 din orasul k de plecare.
- In orice oras unul dintre ei poate lua un taxi, cu care unul dintre ei sa-si continue drumul separat. Despartirea nu necesita timp suplimentar.
- Pe fiecare sosea se circula in ambele sensuri.
- Nu se stationeaza nici un moment din momentul 0 al plecarii.
- Nu sunt permise intoarceri pe soseaua dintre doua orase.

Datele de intrare se gasesc in fisierul input.txt sub forma urmatoare:
n m //doua numere despartite printr-un spatiu reprezentand numarul n de orase aflate pe harta si numarul m de sosele ce leaga orasele de pe harta
k p //doua numere despartite printr-un spatiu reprezentand numarul de ordine al orasului de plecare si numarul natural p de ore pe care il au la dispozitie
i j //doua numere despartite printr-un spatiu reprezentand numerele de ordine al oraselor destinatie pentru fiecare din cei doi indragostiti
i₁ j₁ d₁ //pe urmatoarele m linii cate trei numere naturale despartite printr-un spatiu reprezentand soseaua directa intre orasele i_i si j_i si durata in ore d_i a parcurgerii ei.
---------------------------------------------------------------------------
i_m j_m d_m

Datele de iesire vor fi scrise in fisierul output.txt si va avea doua linii ce vor contine rezultatele sub forma urmatoare:
dmax //numar natural reprezentand durata maxima exprimata in ore, in care cei doi se vor plimba impreuna
k i₁...i_t //reprezentand orasele pe care le vor vizita impreuna, in ordine, incepand cu orasul k de plecare.
Datele vor fi despartite prin cate un spatiu.
In cazul in care solutia optima nu este unica se va afisa o singura solutie.
Datele de intrare sunt astfel concepute incat problema sa aiba solutie.

Exemplu:
Pentru fisierul de intrare input.txt:
8 9
7 8
1 2
1 3 1
3 4 1
4 2 1
4 5 1
4 6 2
5 6 3
6 8 1
7 8 1
7 6 1
Fisierul output.txt va contine:
6
7 8 6 5 4

Timp de executie: 4 secunde pe test.
Punctaj maxim posibil: 75 puncte