Revizia anterioară Revizia următoare
| 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 oricarei muchii este sub 1 000 000
| # | 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, 1 ≤ S, M ≤ 200 000, Graful este un lant |
| 4 | 16 | 1 ≤ N ≤ 100 000, 1 ≤ S, M ≤ 200 000, $1 ≤ Q ≤ 100 |
| 5 | 34 | 1 ≤ N, S ≤ 500 000, 1 ≤ M ≤ 1 000 000 |
Raspunsul pentru fiecare query este <
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 |
