Editing 2539 - flori4


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>