4118 - regate

În tărâmul ONI se află N regate legate între ele prin M muchii bidirecționale. Se garantează că se poate ajunge de la orice regat la oricare alt regat folosind aceste muchii. Aceste regate vor să facă alianțe între ele și se vor folosi de puncte de frontieră pentru a realiza acest lucru.

Fiecare muchie i, unde 1 ≤ i ≤ M, are asociat un număr natural c[i] reprezentând costul construcției unui punct de frontieră pe aceasta. Mai mult decât atât, fiecare regat i, unde 1 ≤ i ≤ N, are asociat un număr natural r[i] reprezentând costul construcției unui punct de frontieră la intrarea acestuia.

Pentru ca regatul X să intre într-o alianță cu regatul Y, unde 1 ≤ X, Y ≤ N, X ≠ Y, acesta are două opțiuni:

• construiește un punct de frontieră pe o singură muchie i cu cost c[i], astfel încât orice drum de la X la Y trece prin acest punct de frontieră;
• construiește un punct de frontieră la intrarea regatului său (regatului X) cu cost r[X].

Evident, regatul X va alege costul minim pentru a intra într-o alianță cu regatul Y. Vom nota acest cost minim cu Cost(X, Y). Atenție, costul ca regatul X să intre într-o alianță cu regatul Y poate fi diferit de costul ca regatul Y să intre într-o alianță cu regatul X!

Pentru ca regatul X să fie într-o alianță perfectă acesta trebuie să facă alianță cu toate celalate regate.

Atenție, în formarea unei alianțe nu se iau în considerare punctele de frontieră construite în formarea altor alianțe. Cu alte cuvinte, Cost(X, Y) se calculează independent pentru fiecare pereche (X, Y)!

Cerința

Pentru fiecare regat trebuie să calculați costul pe care acesta trebuie să-l plătească pentru a fi într-o alianță perfectă. Cu alte cuvinte, pentru fiecare regat i, unde 1 ≤ i ≤ N, trebuie să calculați .

Date de intrare

Pe prima linie a fișierului de intrare regate.in se află N și M, numărul de regate, respectiv, numărul de muchii bidirecționale. Pe a doua linie se găsesc numerele r[1], …, r[N], separate prin spații, unde r[i] reprezintă costul construcției unui punct de frontieră la intrarea regatului i. Pe următoarele M linii se află câte trei numere naturale a[i], b[i], c[i], separate prin spații, 1 ≤ i ≤ M, semnificând că există o muchie bidirecțională între regatul a[i] și regatul b[i], iar c[i] reprezintă costul construcției unui punct de frontieră pe muchia i.

Date de ieșire

În fișierul de ieșire regate.out se vor afișa N linii. Fiecare linie i va conține un singur număr întreg, reprezentând costul ce trebuie plătit pentru ca regatul i să fie într-o alianță perfectă, cu alte cuvinte, .

Restricții și precizări

• 1 ≤ N ≤ 200.000
• 1 ≤ M ≤ 200.000
• 1 ≤ c[i]≤ 1.000.000.000
• 1 ≤ r[i] ≤ 1.000.000.000
• 1 ≤ a[i], b[i] ≤ N, a[i] ≠ b[i] (adică nu există muchie de la un regat la el insuși)
• Între două regate poate exista cel mult o muchie
• Datorită dimensiunilor foarte mari, doar o parte din teste au putut fi folosite.

Exemplu:

regate.in

5 5
8 13 9 7 12
1 2 10
2 3 10
3 4 10
4 5 10
1 3 10

regate.out

32
46
36
28
40

Explicație

De exemplu, pentru regatul 2 avem:

Cost(2, 1) = 13

Cost(2, 3) = 13

Cost(2, 4) = 10

Cost(2, 5) = 10

Suma acestora este 46.

Atenție că, de exemplu, în calculul lui Cost(2, 1), nu putem pune un punct de frontieră pe muchia (1 ,2) de cost 10, deoarece există drumul 2 → 3 → 1 care nu trece prin muchia (1, 2).

Rezolvare

<syntaxhighlight lang="python3"> import heapq

class Graph:

   def __init__(self, n):
       self.n = n
       self.adj_list = [[] for _ in range(n)]

   def add_edge(self, u, v, w):
       self.adj_list[u].append((v, w))
       self.adj_list[v].append((u, w))

   def dijkstra(self, src):
       dist = [float('inf')] * self.n
       dist[src] = 0
       pq = [(0, src)]

       while pq:
           cost, node = heapq.heappop(pq)
           if cost > dist[node]:
               continue
           for neighbor, edge_cost in self.adj_list[node]:
               new_cost = cost + edge_cost
               if new_cost < dist[neighbor]:
                   dist[neighbor] = new_cost
                   heapq.heappush(pq, (new_cost, neighbor))
       return dist

def main():

   # Citire date de intrare
   with open("regate.in", "r") as fin:
       N, M = map(int, fin.readline().split())
       r = list(map(int, fin.readline().split()))
       graph = Graph(N)
       for _ in range(M):
           a, b, c = map(int, fin.readline().split())
           graph.add_edge(a - 1, b - 1, c)

   # Calcul costuri minime pentru fiecare regat
   total_costs = []
   for i in range(N):
       dist = graph.dijkstra(i)
       total_cost = 0
       for j in range(N):
           if i != j:
               min_edge_cost = min(edge_cost for neighbor, edge_cost in graph.adj_list[j])
               total_cost += min(dist[j], r[j], min_edge_cost)
       total_costs.append(total_cost)

   # Scriere rezultate
   with open("regate.out", "w") as fout:
       for cost in total_costs:
           fout.write(str(cost) + "\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>