Danciu: Pagină nouă: Compania lui Jimmy are `n` plantații cu flori. Pentru fiecare plantație se cunoaște tipul florilor cultivate, respectiv câte tone de flori au fost produse anul acesta. Se cunoaște că plantațiile cu flori sunt conectate prin `n - 1` drumuri astfel încât la fiecare plantație se poate ajunge de la oricare altă plantație și există un singur mod de ajunge de la plantația `x` la plantația `y` , pentru fiecare `1 ≤...`


2024-06-04T02:57:25Z
Pagină nouă:  Compania lui Jimmy are <code>n</code> plantații cu flori. Pentru fiecare plantație se cunoaște tipul florilor cultivate, respectiv câte tone de flori au fost produse anul acesta. Se cunoaște că plantațiile cu flori sunt conectate prin <code>n - 1</code> drumuri astfel încât la fiecare plantație se poate ajunge de la oricare altă plantație și există un singur mod de ajunge de la plantația <code>x</code> la plantația <code>y</code> , pentru fiecare <code>1 ≤...
New page


Compania lui Jimmy are <code>n</code> plantații cu flori. Pentru fiecare plantație se cunoaște tipul florilor cultivate, respectiv câte tone de flori au fost produse anul acesta. Se cunoaște că plantațiile cu flori sunt conectate prin <code>n - 1</code> drumuri astfel încât la fiecare plantație se poate ajunge de la oricare altă plantație și există un singur mod de ajunge de la plantația <code>x</code> la plantația <code>y</code> , pentru fiecare <code>1 ≤ x, y ≤ n</code>. De asemenea, știm și distanța în km pentru fiecare dintre cele <code>n - 1</code> drumuri.



= Cerința =

Jimmy vrea să aducă toate florile de același tip în același loc, cu cost minim de transport. Dacă avem <code>a</code> tone de flori şi vrem să le trimitem pe o distanță de <code>b</code> kilometri, costul transportului este <code>a * b</code>. Pentru fiecare tip de floare Jimmy vrea să determine costul minim de transport pentru a aduce toate florile de același tip la un loc.



= Date de intrare =

Pe prima linie se va găsi numărul <code>n</code>, apoi, pe cea de-a doua linie, <code>n</code> litere mici separate între ele prin câte un spațiu, care simbolizează tipul de floare produs pe plantația <code>i</code> (fiecare tip de floare este o literă mică a alfabetului englez). Pe cea de-a treia linie se găsesc <code>n</code> numere întregi care reprezintă câte tone din fiecare floare au fost produse pe plantația <code>i</code>. Pe fiecare dintre următoarele <code>n - 1</code> linii se găsesc trei numere naturale <code>x</code>, <code>y</code>, <code>d</code>, cu semnificația că există drum direct între plantațiile <code>x</code> şi <code>y</code>, iar numărul <code>d</code> reprezintă distanța de la <code>x</code> la <code>y</code>.



= Date de ieșire =

Pe prima linie se afișează <code>26</code> de numere separate prin spațiu, al <code>i</code>-lea număr reprezentând costul minim de transport pentru tipul de floare specificat de litera de pe poziția <code>i</code> în alfabetul englez (răspunsurile sunt în ordinea în care literele se găsesc în alfabet).



= Restricții și precizări =



* <code>4 ≤ n < 200 001</code>.

* Fiecare dintre numerele din datele de intrare este un număr natural mai mic decât <code>200 001</code>.

* Destinaţia finală a fiecărui transport este una dintre cele <code>n</code> plantaţii existente.

* Dacă există litere care nu reprezintă codul tipului unei flori, atunci costul minim de transport pentru acel tip este <code>0</code>.

* Pentru <code>20%</code> din teste, <code>n < 1000</code>.

* Pentru alte <code>25%</code> din teste, <code>n < 100 000</code>.



= Exemplu: =

Intrare

 4

 a b a b

 2 4 4 3

 1 3 4

 3 4 2

 1 2 5

Ieșire

 8 33 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0



== Rezolvare ==

<syntaxhighlight lang="python3">

import heapq





def dijkstra(graph, start):

    n = len(graph)

    dist = [float('inf')] * n

    dist[start] = 0

    pq = [(0, start)]  # Priority queue of tuples (distance, vertex)



    while pq:

        d, u = heapq.heappop(pq)

        if d > dist[u]:

            continue

        for v, w in graph[u]:

            if dist[u] + w < dist[v]:

                dist[v] = dist[u] + w

                heapq.heappush(pq, (dist[v], v))



    return dist





def calculate_transport_cost(types, quantities, distances):

    n = len(types)

    types_cost = [0] * 26



    for t in range(26):

        nodes = {i for i in range(n) if ord(types[i]) - ord('a') == t}

        if not nodes:

            continue



        dist = dijkstra(distances, next(iter(nodes)))  # Selectăm primul nod din set

        for i in range(n):

            if ord(types[i]) - ord('a') == t:

                types_cost[t] += quantities[i] * dist[i]



    return types_cost





n = int(input())

types = input().split()

quantities = list(map(int, input().split()))



distances = [[] for _ in range(n)]

for _ in range(n - 1):

    x, y, d = map(int, input().split())

    distances[x - 1].append((y - 1, d))

    distances[y - 1].append((x - 1, d))



result = calculate_transport_cost(types, quantities, distances)





print(*result)



</syntaxhighlight>
2539 - flori4 - Revision history
