| Fişierul intrare/ieşire: | nolife.in, nolife.out | Sursă | Lot Mehedinți 2015 - Baraj 5 Seniori |
| Autor | Mihai Ciucu | Adăugată de |  Tatomir Alex •atatomir |
| Timp execuţie pe test | 5 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
NoGameNoLife - The Final Stage
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.
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.
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.
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
Exemplu
| 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. |
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:
Ş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.
Atentie! Datorita imposibilitatii de a obtine scorul de 100 de puncte , evaluatorul va va oferi un punctaj normalizat cu cel al sursei oficiale.Astfel acesta va fi calculat dupa formula : 
