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

<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>