Doi prieteni se afla într-un
oras k si au la dispozitie p
ore, timp în care sa se plimbe cu masina si apoi sa ajunga fiecare la el acasa,
fata în orasul X, iar baiatul
în orasul Y.
Ei doresc sa se plimbe
cât mai mult timp împreuna, dar sa ajunga în cel mult p
ore, fiecare în orasul sau. Masina se deplaseaza cu viteza constanta (cea legal
admisa).
Cei doi au la dispozitie
o harta cu n orase printre care
se afla, evident, orasul de plecare k
si orasele destinatie X si Y.
Harta indica orasele legate prin sosele si durata exprimata în ore a parcurgerii
cu viteza constanta (legal admisa) a distantei dintredoua orase.
Cerinta
Sa se determine traseul
comun pe care îl vor parcurge cei doi prieteni astfel încât timpul petrecut
împreuna sa fie maxim si sa ajunga amândoi la propria destinatie în cel mult
p ore de la plecare.
Date de intrare
Pe prima linie a fisierului
de intrare masina1.in se afla
doua numere naturale n si m
despartite printr-un spatiu, reprezentând numarul de orase de pe harta si numarul
de sosele ce leaga aceste orase. Pe
cea de a doua linie se afla doua numere naturale k
si p, despartite printr-un spatiu,
reprezentând numarul de ordine al orasului de plecare si numarul de ore pe care
le au la dispozitie cei doi prieteni. Pe
cea de a treia linie sunt scrise doua numere naturale X
si Y despartite printr-un spatiu,
reprezentând numerele de ordine ale oraselor de destinatie pentru cei doi. Pe urmatoarele m linii sunt scrise triplete de numere naturale a
b d, (0<d<=p) despartite
prin câte un spatiu, reprezentând faptul ca între orasele a
si b exista sosea directa, respectiv
durata d a parcurgerii acesteia,
exprimata în ore.
Date de iesire
Pe
prima linie a fisierului de iesire masina1.out
va fi scris un numar natural dmax,
reprezentând durata maxima (exprimata în ore) în care ceidoi se vor
plimba împreuna. Pe cea de a doua linie vor fi scrise in ordine orasele pe care
le vor vizita impreuna (separate prin cate un spatiu), incepand cu orasul de
plecare k.
Restrictii si precizari
p<=150
2<n<=200 În cazul în care solutia
optima nu este unica, se va afisa una singura.
Cronometrarea duratei plimbarii se face începând cu momentul 0 din orasul de plecare k.
In orice oras unul dintre ei poate continua drumul separat, cu o alta masina; (despartirea nu
necesita timp suplimentar).
Pe fiecare sosea se circula în ambele sensuri.
Dupa plecarea din orasul k nu se stationeaza nici un
moment.
Nu sunt permise parcurgeri incomplete ale unei sosele ce leaga doua orase.