== include(page="template/taskheader" task_id="nolife") ==
După ce au cucerit toate cele $16$ rase, Sora şi cu Shiro în sfârşit au ajuns sa îl provoace pe zeul Tet la duel. Tet a generat aleator un graf neorientat cu costuri pe muchii. La sfârşit, acesta le-a pus celor doua personaje $Q$ întrebări de forma: care este drumul de lungime minima de la nodul $x$ la nodul $y$? Pentru că ştie ca este o problema grea, el se mulţumeşte cu drumuri cât mai scurte, nu neapărat cele mai scurte.
Poveste şi cerinţă...
h2. Date de intrare
Pe prima linie a fişierului de intrare $nolife.in$ se va afla un număr natural $N$ (numărul de noduri) şi un numar natural $M$ (numărul de muchii). Pe următoarele $M$ linii vor fi trei numere $x$, $y$ şi $z$, reprezentând faptul că există muchie între nodurile $x$ şi $y$ de lungime $$z. Pe următoarea linie se va afla un singur numar natural $Q$. Pe urmatoarele $Q$ linii vor fi câte două numere, $x$ şi $y$ – nodurile între care vrea să găsim un drum cât mai scurt.
Fişierul de intrare $nolife.in$ ...
h2. Date de ieşire
În fişierul de ieşire $nolife.out$ se va afişa răspunsul pentru fiecare întrebare, câte unul pe linie. Un răspuns trebuie să descrie un drum între nodurile $x$ şi $y$ în felul următor: Primul număr de pe linie este numărul de noduri prin care trece drumul, urmat de nodurile în ordinea de parcurgere de la $x$ la $y$. În cazul în care vreţi să nu răspundeţi la o întrebare, afişaţi doar $0$ pentru aceasta.
În fişierul de ieşire $nolife.out$ ...
h2. Restricţii
* $1 ≤ N ≤ 100.000$
* $1 ≤ M ≤ 300.000$
* $1 ≤ Q ≤ 20.000$
* $Pentru că e demiurg programator, Tet indexează indicii nodurilor de la 0 la N-1$
* $Se garantează că există drum între toate nodurile din întrebari$
* $Cel mai bun concurent o să o câştige pe Jibril$
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. nolife.in |_. nolife.out |_. Explicatie |
| 5 6
1 2 1
1 4 2
4 3 4
2 3 2
4 0 3
3 0 6
4
1 2
2 0
1 4
3 4
| 2 1 2
4 2 1 4 0
2 1 4
2 3 4
| Această soluţie primeşte punctaj complet pe test, deoarece toate drumurile sunt optime.
|
h3. Punctare
Tet ştie că viaţa e o competiţie, aşa că vă va puncta în felul următor: Pentru fiecare test veţi primi un scor brut, care reprezintă suma scorurilor pentru fiecare întrebare. Pentru fiecare întrebare primiţi $1$ punct dacă aflaţi un drum de lungime optimă, altfel veţi primi un număr de puncte calculat după formula:
!problema/nolife?img.png!
Ştim că sună complicat, dar doar vrea să zică că primiţi maxim $0.9$ puncte pentru orice scor neoptim, iar la fiecare abatere de $25%$ de la optim vi se înjumătăţeşte punctajul.
table(example). |_. nolife.in |_. nolife.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="nolife") ==
