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

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


Timp maxim de executie/test:
3.5 secunde
Memorie totala disponibila/stiva:
15 MB/1 MB

Soarta lui Vasile a fost crunta. Dupa câteva aventuri de tip Caritas a ajuns un biet homeless. Acum e inca iarna, e frig si Vasile s-a gândit ca ar fi bine sa isi cumpere un abonament CFR, macar sa poata dormi in vagoane incalzite si sa viseze la o viata mai buna.

Vasile a analizat harta CFR si a identificat N statii de cale ferata (pe care le-a numerotat de la 1 la N) si P tronsoane de cale ferata. Un tronson realizeaza legatura bidirectionala intre doua statii, lungimea unui tronson fiind egala cu timpul necesar trenului sa ajunga dintr-o statie in cealalta.

De asemenea Vasile a studiat si mersul trenurilor si cunoaste pentru fiecare tren timpul la care pleaca din prima statie de pe ruta sa (exprimat in secunde) si statiile prin care trece. Trenurile opresc in toate statiile prin care trec, timpul de stationare fiind neglijabil. Când doua trenuri se afla in aceeasi statie, Vasile poate sa sara dintr-un tren in altul, fara a pierde timp suplimentar.

Initial (secunda 1) Vasile se afla in statia cu numarul 1. Vasile pleaca din statia 1 si trebuie sa se intoarca in statia 1 in intervalul de timp [T1, T2], timpii T1 si T2 fiind exprimati in secunde. El se deplaseaza numai cu trenul, poate cobori din tren in orice statie prin care trece trenul respectiv, se poate urca intr-un tren in oricare dintre statiile prin care trece trenul respectiv (cu conditia ca Vasile sa se afle in statie la momentul in care trenul soseste).

Cerinta

Scrieti un program care sa determine timpul total minim de asteptare in statii, in conditiile in care Vasile trebuie sa calatoreasca cu trenurile existente si sa revina in statia 1 in intervalul de timp [T1, T2].

Date de intrare

Fisierul de intrare homeless.in contine:
- pe prima linie 5 numere intregi N P V T1 T2, separate prin spatii (N reprezinta numarul de statii, P este numarul de tronsoane, V este numarul de trenuri, iar T1 si T2 au semnificatia din enuntul problemei).
- fiecare dintre urmatoarele P linii contine informatii despre un tronson sub forma a 3 numere intregi separate prin spatii S1 S2 T cu semnificatia "tronsonul leaga statiile S1 si S2, durata calatoriei pe acest tronson fiind T secunde".
- fiecare dintre urmatoarele V linii contine informatii despre un tren. Primul numar de pe linia corespunzatoare unui tren este T0, care reprezinta timpul de plecare a trenului din prima statie (exprimat in secunde), al doilea numar este NS care reprezinta numarul de statii de pe ruta acestui tren (inclusiv statia de plecare si cea de sosire), iar urmatoarele NS numere reprezinta in ordine numerele statiilor prin care trece trenul. Trenul pleaca de la prima statie si se opreste la ultima statie de pe ruta sa, iar la ultima statie toti calatorii trebuie sa coboare. Toate numerele de pe linie sunt separate prin câte un spatiu.

Date de iesire

Fisierul de iesire homeless.out va contine o singura linie pe care va fi scris timpul total minim de asteptare in statii.

Restrictii

  • 1 < N, V < 1001
  • 0 < T1 <= T2 <= 50000
  • 0 < durata calatoriei pe orice tronson T < 601
  • 0 < numarul de statii de pe ruta oricarui tren NS < 1001

Exemplu

homeless.in homeless.out homeless.in homeless.out
4 4 3 30 35
1 2 5
2 3 2
2 4 7
3 4 3
2 4 1 2 4 3
14 4 3 4 2 3
28 3 3 2 1
6 4 6 5 80 100
4 2 6
2 1 16
1 3 17
1 4 19
4 3 9
3 2 10
25 3 1 3 2
25 3 1 2 4
4 4 1 2 3 4
52 4 4 2 1 4
64 4 2 3 4 1
22

prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2003: newcomp, rima, algebra, turn1, aparitii, carti1, program1, tgraf, ceas1, spioni, kgb, tabara1, romane, stop, hanoi, lift, pic, sms, fibo, bac, parc, circular, logn, lex, joc7, cuburi1, sant, mobile, pattern, oras, produs, mutare, viteza, concurs2, furnici, subsir
De acelaşi autor: celule, scp, vedete, film, ab, supertri, inginer, camp, sl, detinut, simetric, egal, gropi, ruleta, carti, tgv, uscat, afise, dezbateri, bunici, rv, onu, nspecial, secvop, cadou, chimie, reteta, piticot, petrol, checkin, teanc, index, teren, pizza, ecran, drum, text, lbd, aven, spam, pluricex, tren2, gray, pasi, mgo, joc, anagrame, vecini, criptmat, maxim, cutie, party, friends, net, sablon, hd, pc, sir2, aztec, scara, nr, robot2, sah, formule, ed, bilete, hanoig, flood, matrice3, erdos, grup, cd, kfactor, np, cuc, radio, honest, ref, nr01, scor2, convert, auto2, compress, politics, pm, playlist, barbie, firma1, submatrix, ham, pizza1, exam, ants, teatru1, cifre1, bile1, caini, secvreg, pasune, remi, m01, sir23, tren1, joc5, pachete, aedaro, windows, renju, latime, mere1, piloti, peste, pitici, sirag1, stive, turn1, carti1, program1, spioni, kgb, lift, apel, lex, oras, subsir, dist, harta1, adevar, joc10, bare, zapezi, masina2, perechi1, raft, joc11, joc12, ferma, fni, tunel, lover, pepsi, transport, avion, monkey, premii1, garaj, carti2, tv, pact, fat, cafea, echipe1, secvente, petrom, peg, scara1, lant, ecuatii, stiva, bile4, jungla, rj, poli, text1, compus1, rez, politie, anag, codul, coment, muzeu, seti, basm, timer, secvsir, dp, placa, prod3, bursa, submdisj, sotron1, fazan, secvpar, joker, lego, medalii, cfr, antipatie, figura, links, segm, colorare, brazi, mobil, distsir, guess, greiere, pestera, conferinta, chei, ny, nx, ghinion, sumb, drenaj, telecomanda, grupuri, mahjong, rotund, viena, sport2, cos, monoton, micro, valet, nr0, maxviz, anagramabil, nrpal, lista, dame, consiliu, adprod, arme, deal, prodnr, compar, latin, interviu, vintage, prize, nrdiv, arrows, tdrept, agenda, reziston, vot2, tema, smiley, relatii, ech, scadere, nebuni, castig, expand, wb, prime2, virgule, b210
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, masina1, bomboane, turn1, shgraf, paintball, program1, tgraf, kgb, algola, felinar, joc6, tric, 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
Software recomandat
surse trimise | ajutor