2539 - flori4

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 ≤ x, y ≤ n. De asemenea, știm și distanța în km pentru fiecare dintre cele n - 1 drumuri.

Cerința

Jimmy vrea să aducă toate florile de același tip în același loc, cu cost minim de transport. Dacă avem a tone de flori şi vrem să le trimitem pe o distanță de b kilometri, costul transportului este a * b. 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 n, apoi, pe cea de-a doua linie, n litere mici separate între ele prin câte un spațiu, care simbolizează tipul de floare produs pe plantația i (fiecare tip de floare este o literă mică a alfabetului englez). Pe cea de-a treia linie se găsesc n numere întregi care reprezintă câte tone din fiecare floare au fost produse pe plantația i. Pe fiecare dintre următoarele n - 1 linii se găsesc trei numere naturale x, y, d, cu semnificația că există drum direct între plantațiile x şi y, iar numărul d reprezintă distanța de la x la y.

Date de ieșire

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

Restricții și precizări

• 4 ≤ n < 200 001.
• Fiecare dintre numerele din datele de intrare este un număr natural mai mic decât 200 001.
• Destinaţia finală a fiecărui transport este una dintre cele n plantaţii existente.
• Dacă există litere care nu reprezintă codul tipului unei flori, atunci costul minim de transport pentru acel tip este 0.
• Pentru 20% din teste, n < 1000.
• Pentru alte 25% din teste, n < 100 000.

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

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)