.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » masina1

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
masina1


Timp maxim de executie/test:
0.2 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

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 dintre doua 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 cei doi 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.

Exemplu

masina1.in masina1.out
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
6
7 6 5 4 3

Prof. Dana Lica
Colegiul National "I.L. Caragiale" Ploiesti
Contact: danal182001@yahoo.com

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2004: cifre1, super, apm, bile1, factk, schimb, caini, secvreg, descfib, maraton, otilia, multiplu, tub, pasune, remi, m01, robot1, na, sir23, paralel, zaruri, bomboane, dotnet, divizor, tren1, joc5, tvshow, pachete, soldati1, echipe, omizi, suma1, aedaro, concurs1, windows, comb, renju, latime, vectori, ghici, subperm, puncte, mere1, spirala, distanta, piloti
De acelaşi autor: compus, taste, arce, balbe, drept, scor, sume3, spair, bitslang, police, tree, reteta2, farfurii, caramele, apm, maraton, bomboane, soldati1, concurs1, puncte, pipe, camion, imax, litoral, dreptc, bal, prefix1, tablite, lanturi, loto, bila, popic, activ, game1, pitag, secv9, divk, taler, bdotcom, oak, ozn1, optim, puncte5, swap, tetris3, monede2, ssk
Despre graf: gropi, tgv, matrice2, miniasm, picnic, mere, circuit, soldati, arce, conflicte, desen, robot, furtuna, net, cuvinte, excursie, cadere, pioni, reinvent, kreg, flood, croco, johnie, matrice, arthur, kimberley, ro, sol, caravane, bete, honest, police, pcod, zmeu, auto2, grazing, datorii, trafic, sponsori, monede1, apm, bile1, caini, bomboane, turn1, shgraf, paintball, program1, tgraf, kgb, algola, felinar, joc6, tric, homeless, promo, turism, casute, joc10, prieteni1, traseu, zapezi, litoral, lover, trip, garaj, ziduri, tv, pact, echipe1, vitale, spion, trasee, bcolor, scara2, lant, ab3, soc, team, gard, rsp, graf, mexc, dep, albinuta1, atac2, cabane, drumuri, tj, grade, jungla, lanterna, magic5, coment, urgenta, fazan, lanturi, cfr, site, traseu1, trmv, graphgame, minuni, telefon, ubergraf, carray, pestera, chei, arbgraf, war, fluviu, drumuri1, entries, ubuntzei, pack, fotbal1, pamant, dag, razboi, benzina2, wg, neconex, asfalt1, kubus2, module, progresii, dfs, prieteni3, megascoala, grafxy, dineu, vot1, biperm, drumuri2, nrgraf, cristal, cartite, copaci3, dragoni, nuclee
Despre drum minim: miniasm, robot, furtuna, excursie, arthur, bete, zmeu, trafic, bomboane, traseu, litoral, lover, trip, scara2, team, gard, pitici1, base3, coach, lanturi, trmv, pestera, fluviu, ubuntzei, razboi, benzina2, kubus2, megascoala, dragoni
surse trimise | ajutor