Zmeul le-a inchis pe cele
5 fete ale imparatului in castelul sau. Fat-Frumos a venit sa le scoata din
castel, folosind harta pe care i-a dat-o zana buna. Pe harta sunt desenate cele
n camere ale castelului, numerotate
de la 1 la n
si cele m tuneluri dintre camere.
De asemenea sunt marcate camerele in care se gasesc fetele si Fat-Frumos, timpul
necesar traversarii fiecarui tunel si cele p
camere din care se poate iesi din castel.
Cerinta
Determinati timpul minim necesar lui Fat-Frumos pentru a lua cele 5 fete si a le scoate din castel.
Date de intrare
Pe prima linie a fisierului
de intrare zmeu.in sunt
scrise numerele n, m
si p, reprezentand numarul de
camere, numarul de tunele si respectiv numarul de iesiri din castel.
Pe a doua linie sunt scrise numerele a 6 camere distincte: primul numar e camera
in care se afla Fat-Frumos, iar celelalte 5 sunt camerele fetelor.
Pe urmatoarele m linii sunt cate
3 numere, reprezentand cele m
tunele: primele doua reprezinta camerele intre care face legatura tunelul, al
treilea timpul necesar traversarii tunelului.
Ultimele p linii contin cate
un numar reprezentand camerele din care se poate iesi din castel. Toate numerele
sunt intregi strict pozitive, iar numerele de pe aceeasi linie sunt separate
prin cate un spatiu.
Date de iesire
Prima linie a fisierului
zmeu.out
va contine un singur numar, timpul minim necesar pentru a porni din camera
lui Fat-Frumos, a trece prin camerele celor 5 fete si a ajunge intr-o camera
care are iesire in afara. Se va lua in considerare numai timpul traversarii
tunelurilor, neglijandu-se timpul traversarii camerelor sau a iesirii din castel.
Restrictii
4 <=n <= 1000
1 <= m <= n*(n-1)/2
1 <= p <= n/2
Timpul de traversare a unui tunel
este un numar intreg din intervalul [1,200]
Initial in nici o camera nu se afla mai mult de o persoana.
Intotdeauna va exista o posibilitate de salvare a fetelor.