Pagini recente » Diferente pentru algoritmiada-2012/runda-4/10 intre reviziile 3 si 1 | Monitorul de evaluare | Diferente pentru problema/drum7 intre reviziile 17 si 9 | Diferente pentru utilizator/danielp intre reviziile 23 si 24 | Diferente pentru problema/drum-bugetat intre reviziile 9 si 10
Nu exista diferente intre titluri.
Diferente intre continut:
A fost odata ca niciodata tinutul lui Rosu Imparat, unde traiau Harap-Alb si Ileana Cosanzeana care, fiind indragostiti, se intalneau foarte des desi stateau in orase diferite.
La inceput totul a fost perfect, intrucat Harap-Alb era un tanar destept si stia sa aleaga drumul cel mai scurt pana la casa Ileanei folosind algoritmii invatati la facultate.
Totusi, situatia s-a schimbat de cand imparatul Rosu a decis sa taxeze trecerea prin orase cu un numar de galbeni. Astfel, Fat-Frumos si-a dat seama ca bugetul personal nu ii ajunge intotdeauna daca foloseste cel mai scurt drum pentru a ajunge la Ileana Cosanzeana.
Stiind ca Fat-Frumos stie perfect harta imparatiei data prin N - numarul de orase, si M - numarul de drumuri directe intre orase pe care se poate circula in ambele sensuri, si avand la dispozitie bugetul de care dispune Fat-Frumos pentru a calatori, B, ajutati-l sa descopere cum poate ajunge pana in orasul unde locuieste Ileana Cosanzeana, t, stiind ca la inceput Fat Frumos este in orasul s. Pentru ca vrea sa o vada pe Ileana cat mai repede, Fat-Frumos prefera sa foloseasca cea mai scurta cale pentru care are bugetul necesar pentru a plati taxele de transport din fiecare oras prin care trece (mai putin sursa, dar incluzand destinatia). Daca exista mai multe astfel de drumuri, evident ca el va prefera drumul cel mai ieftin pentru ca ii raman mai multi bani pentru a iesi in oras cu prietena lui.
Stiind ca Fat-Frumos stie perfect harta imparatiei data prin $N$ - numarul de orase, si $M$ - numarul de drumuri directe intre orase pe care se poate circula in ambele sensuri, si avand la dispozitie bugetul de care dispune Fat-Frumos pentru a calatori, $B$, ajutati-l sa descopere cum poate ajunge pana in orasul unde locuieste Ileana Cosanzeana, t, stiind ca la inceput Fat Frumos este in orasul s. Pentru ca vrea sa o vada pe Ileana cat mai repede, Fat-Frumos prefera sa foloseasca cea mai scurta cale pentru care are bugetul necesar pentru a plati taxele de transport din fiecare oras prin care trece (mai putin sursa, dar incluzand destinatia). Daca exista mai multe astfel de drumuri, evident ca el va prefera drumul cel mai ieftin pentru ca ii raman mai multi bani pentru a iesi in oras cu prietena lui.
h2. Date de intrare
Fisierul de intrare $drum-bugetat.in$ contine:
* pe primul rand se afla trei numere intregi: N - numarul de orase, M - numarul de drumuri directe intre orase, si B - numarul de galbeni pe care ii are la dispozitie Fat-Frumos .
* pe al doilea rand se afla alte doua numere intregi: s - orasul in care se afla Harap-Alb, si t - orasul in care se afla Ileana Cosanzeana.
* pe urmatorul rand se afla N numere intregi care reprezinta costurile de trecere (numarul de galbeni care trebuie platiti) prin cele N orase (primul oras apare la inceput, orasul N este ultimul).
* pe urmatoarele M randuri sunt 3 numere: primele doua reprezinta orasele intre care exista acest drum direct, iar al treilea este lungimea drumului respectiv.
* pe primul rand se afla trei numere intregi: $N$ - numarul de orase, $M$ - numarul de drumuri directe intre orase, si $B$ - numarul de galbeni pe care ii are la dispozitie Fat-Frumos .
* pe al doilea rand se afla alte doua numere intregi: $s$ - orasul in care se afla Harap-Alb, si $t$ - orasul in care se afla Ileana Cosanzeana.
* pe urmatorul rand se afla $N$ numere intregi care reprezinta costurile de trecere (numarul de galbeni care trebuie platiti) prin cele $N$ orase (primul oras apare la inceput, orasul $N$ este ultimul).
* pe urmatoarele $M$ randuri sunt $3$ numere: primele doua reprezinta orasele intre care exista acest drum direct, iar al treilea este lungimea drumului respectiv.
h2. Date de iesire
* $0 ≤ N ≤ 1000$
* $0 ≤ M ≤ 10000$
* $0 ≤ B ≤ 1000$
* lungimea unui drum direct intre 2 orase adiacente : $0$ .. $1000$
* taxa pentru a trece printr-un oras: 0 .. B
* lungimea unui drum direct intre $2$ orase adiacente : $0$ .. $1000$
* taxa pentru a trece printr-un oras: $0$ .. $B$
h2. Observatii
* In fisierul de intrare, orasele sunt numerotate de la 1 la N.
* In fisierul de intrare, orasele sunt numerotate de la $1$ la $N$.
* Daca nu exista nici un drum se afiseaza @"-1"@ (fara ghilimele).
h2. Exemplu
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.