| Fişierul intrare/ieşire: | ghoberdist.in, ghoberdist.out | Sursă | Baraj Shumen Seniori ICHB-Vianu - 2022 |
| Autor | Peticaru Alexandru | Adăugată de |  Comisie Seniori Vianu ICHB •comisie_baraj_shumen_ichb_vianu_seniori |
| Timp execuţie pe test | 0.5845 sec | Limită de memorie | 420690 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Ghober-distante
Esti Ghober-prost sa mor eu
Friedrich Nietzsche
Dupa ce GhoberBoss a ghober-autizat la ghober-concurs va da aceasta ghober-problema ca ghober-razbunare:
Ai un graf conex cu N noduri si M muchii ponderate. Costul unui drum este egal cu costul maxim al unei muchii de pe acesta.
Definim functia f(x, y) = costul minim al unui drum de la x la y. Se dau Q query-uri de forma: K a1 a2 ... ak. Se cere pentru fiecare query suma de f(ai, aj) pentru fiecare pereche (i, j) unde 1 ≤ i < j ≤ k.
Date de intrare
Pe prima linie a fişierului de intrare ghoberdist.in se afla numerele N si M. Pe urmatoarele M linii se alfa 3 numere x y z care inseamna ca exista o muchie intre nodurile x si y cu costul z. Pe urmatoarea linie se afla Q, iar pe urmatoarele Q linii se afla query-urile in formatul K a1 a2 ... ak.
Date de ieşire
În fişierul de ieşire ghoberdist.out se vor afisa Q linii, cu cate un numar, reprezentand raspunsul la fiecare query.
Restricţii
- Fie S = suma tuturor K-urilor de la intrare.
- Costul fiecarei muchii este mai mic sau egal decat 1 000 000
- Raspunsul se incadreaza intr-un tip de date cu 64 de biti cu semn
- Pentru orice subtask, daca nu este precizat, K ≥ 2, si implicit 2 * Q ≤ S
| # | Punctaj | Restricţii |
|---|---|---|
| 1 | 8 | 1 ≤ N, M, S ≤ 1 000 |
| 2 | 23 | 1 ≤ N ≤ 100 000, 1 ≤ S, M ≤ 200 000, K = 2 |
| 3 | 19 | 1 ≤ N ≤ 100 000, M = N-1, 1 ≤ S ≤ 200 000, Graful este un lant |
| 4 | 16 | 1 ≤ N ≤ 100 000, 1 ≤ S, M ≤ 200 000, 1 ≤ Q ≤ 200 |
| 5 | 34 | 1 ≤ N, S ≤ 500 000, 1 ≤ M ≤ 1 000 000 |
Exemplu
| ghoberdist.in | ghoberdist.out |
|---|---|
| 7 10 1 4 6 1 5 10 1 6 10 1 7 11 2 5 8 2 7 9 3 4 5 3 5 11 4 7 9 5 6 9 3 4 2 3 5 7 5 3 1 4 7 6 2 1 4 | 53 80 6 |
