Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | peapesimaitulburi.in, peapesimaitulburi.out | Sursă | Concursul National de Informatica "Adolescent Grigore Moisil" 18 |
| Autor | Vlad-Andrei Munteanu | Adăugată de |  AGMInformatica •AGMinformatica |
| Timp execuţie pe test | 0.75 sec | Limită de memorie | 300384 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Pe ape si mai tulburi
Se da un graf orientat cu n noduri si m muchii si costuri pe muchii. Se mai dau 3 liste de noduri A, B si C. Pentru fiecare nod din lista A se cere costul minim cu care poate ajunge intr-un nod din lista C cu restrictia ca trebuie sa treaca mai intai printr-un nod din lista B. Daca se intra in ciclu infinit, se afiseaza "-INF", iar dca nu se poate ajunge, se afiseaza "INF". In cazul in care pentru un nod A se poate ajunge atat intr-un C, cat si intr-un ciclu negativ din care nu se mai poate ajunge ulterior intr-un C, se va alege drumul care ajunge la C. Cu alte cuvinte, un ciclu negativ se ia in calcul numai in cazul in care se poate ajunge la un C ulterior din acesta. De asemenea, daca dintr-un nod A nu se poate iesi, dar se poate ajunge intr-un ciclu negativ, raspunsul este INF, deoarece NU se poate iesi. Prioritate are iesirea, apoi costul :)
Date de intrare
Fişierul de intrare peapesimaitulburi.in ...
n m
sursa destinatie cost (m astfel de perechi)
cate_noduri_in_A
A1 A2 A3...
cate_noduri_in_B
B1 B2 B3...
cate_noduri_in_C
C1 C2 C3...
Date de ieşire
În fişierul de ieşire peapesimaitulburi.out ...
Ans1
Ans2
.... (pentrui fiecare nod A)
h2. Restricţii
- ... ≤ ... ≤ ...
1 <= n <= 1e5
1 <= m <= 2e5
-1e5 <= cost <= 1e5
0 <= noduri A, noduri B, noduri C <= n
Se garanteaza ca o muchie X Y poate avea cost negativ daca si numai daca numarul de perechi de noduri U V cu proprietatea ca se poate ajunge atat din U in V cat si din V in U este <= 2500
h2. Exemplu
| peapesimaitulburi.in | peapesimaitulburi.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
