Nu aveti permisiuni pentru a descarca fisierul grader_test9.in
Diferente pentru problema/ghoberdist intre reviziile #11 si #12
Nu exista diferente intre titluri.
Diferente intre continut:
== include(page="template/taskheader" task_id="ghoberdist") == Dupa ce GhoberBoss a ghober-autizat la ghober-concurs va da aceasta ghober-problema. 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 a{~1~} a{~2~} ... a{~k~}$. Se cere pentru fiecare query suma de $f(a{~i~}, a{~j~})$ pentru fiecare pereche $(i, j)$ unde $1 ≤ i < j ≤ k$.
Definim functia $f(x, y)$ = costul minim al unui drum de la $x$ la $y$. Se dau Q query-uri de forma: $K a{~1~} a{~2~} ... a{~k~}$. Se cere pentru fiecare query suma de $f(a{~i~}, a{~j~})$ pentru fiecare pereche $(i, j)$ unde $1 ≤ i < j ≤ k$. Fie S = suma dupa K.
h2. Date de intrare
h2. Restricţii table(restrictii). |_. # |_. Punctaj |_. Restricţii |
| $1$ | $8$ | $1 ≤ N, Q, ≤ $ | | $2$ | $20$ | $31 ≤ N ≤ 120$ | | $3$ | $70$ | $121 ≤ N ≤ 1 000$ |
| $1$ | $8$ | $1 ≤ N, M, S ≤ 1000$ | | $2$ | $23$ | $1 ≤ N, S ≤ 100000, 1 ≤ M ≤ 100000$ arborele este lant| | $3$ | $19$ | $121 ≤ N ≤ 1 000$ | | $4$ | $26$ | $121 ≤ N ≤ 1 000$ | | $5$ | $22$ | $121 ≤ N ≤ 1 000$ |
h2. Exemplu
