Vizualizare sursă pentru „4118 - regate”

În tărâmul ONI se află <code>N</code> regate legate între ele prin <code>M</code> 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 <code>i</code>, unde <code>1 ≤ i ≤ M</code>, are asociat un număr natural <code>c[i]</code> reprezentând costul construcției unui punct de frontieră pe aceasta. Mai mult decât atât, fiecare regat <code>i</code>, unde <code>1 ≤ i ≤ N</code>, are asociat un număr natural <code>r[i]</code> reprezentând costul construcției unui punct de frontieră la intrarea acestuia.

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

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

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

Pentru ca regatul <code>X</code> 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, <code>Cost(X, Y)</code> se calculează independent pentru fiecare pereche <code>(X, Y)</code>!

= 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 <code>i</code>, unde <code>1 ≤ i ≤ N</code>, trebuie să calculați .

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

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

= Restricții și precizări =

* <code>1 ≤ N ≤ 200.000</code>
* <code>1 ≤ M ≤ 200.000</code>
* <code>1 ≤ c[i]≤ 1.000.000.000</code>
* <code>1 ≤ r[i] ≤ 1.000.000.000</code>
* <code>1 ≤ a[i], b[i] ≤ N</code>, <code>a[i] ≠ b[i]</code> (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: =
<code>regate.in</code>
 5 5
 8 13 9 7 12
 1 2 10
 2 3 10
 3 4 10
 4 5 10
 1 3 10
<code>regate.out</code>
 32
 46
 36
 28
 40

=== Explicație ===
De exemplu, pentru regatul <code>2</code> avem:

<code>Cost(2, 1) = 13</code>

<code>Cost(2, 3) = 13</code>

<code>Cost(2, 4) = 10</code>

<code>Cost(2, 5) = 10</code>

Suma acestora este <code>46</code>.

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

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