Paired Payment (Codeforces 1486E)
Tags: Others, flows

There are $$$n$$$ cities and $$$m$$$ bidirectional roads in the country. The roads in the country form an undirected weighted graph. The graph is not guaranteed to be connected. Each road has it's own parameter $$$w$$$. You can travel through the roads, but the government made a new law: you can only go through two roads at a time (go from city $$$a$$$ to city $$$b$$$ and then from city $$$b$$$ to city $$$c$$$) and you will have to pay $$$(w_{ab} + w_{bc})^2$$$ money to go through those roads. Find out whether it is possible to travel from city $$$1$$$ to every other city $$$t$$$ and what's the minimum amount of money you need to get from $$$1$$$ to $$$t$$$.

Input: First line contains two integers $$$n$$$, $$$m$$$ ($$$2 \leq n \leq 10^5$$$, $$$1 \leq m \leq min(\frac{n \cdot (n - 1)}{2}, 2 \cdot 10^5)$$$).Next $$$m$$$ lines each contain three integers $$$v_i$$$, $$$u_i$$$, $$$w_i$$$ ($$$1 \leq v_i, u_i \leq n$$$, $$$1 \leq w_i \leq 50$$$, $$$u_i \neq v_i$$$). It's guaranteed that there are no multiple edges, i.e. for any edge $$$(u_i, v_i)$$$ there are no other edges $$$(u_i, v_i)$$$ or $$$(v_i, u_i)$$$.

Output: For every city $$$t$$$ print one integer. If there is no correct path between $$$1$$$ and $$$t$$$ output $$$-1$$$. Otherwise print out the minimum amount of money needed to travel from $$$1$$$ to $$$t$$$.

Note: The graph in the first example looks like this.In the second example the path from $$$1$$$ to $$$3$$$ goes through $$$2$$$, so the resulting payment is $$$(1 + 2)^2 = 9$$$.

Sample Inputs:
5 6
1 2 3
2 3 4
3 4 5
4 5 6
1 5 1
2 4 2

3 2
1 2 1
2 3 2

Sample Outputs:
0 98 49 25 114

0 -1 9

Solution (Python):
import sys
input = sys.stdin.buffer.readline
from heapq import heappush, heappop
(n, m) = map(int, input().split())
adj = [[] for i in range(n + 1)]
mx_dist = 10 ** 9
dist = [mx_dist] * (51 * (n + 1))
dist[51 * 1] = 0
for i in range(m):
    (u, v, w) = map(int, input().split())
    adj[u].append((v, w))
    adj[v].append((u, w))
h = [(0, 51 * 1)]
while h:
    (d, c) = heappop(h)
    if dist[c] == d:
        (c, last_w) = divmod(c, 51)
        for (ne, w) in adj[c]:
            if last_w:
                new_d = d + (w + last_w) ** 2
                if dist[51 * ne] > new_d:
                    dist[51 * ne] = new_d
                    heappush(h, (new_d, 51 * ne))
            elif dist[51 * ne + w] > d:
                dist[51 * ne + w] = d
                heappush(h, (d, 51 * ne + w))
sys.stdout.write(' '.join([str(dist[51 * i]) if dist[51 * i] != mx_dist else '-1' for i in range(1, n + 1)]))

Solution (Python):
import sys
input = sys.stdin.buffer.readline
from heapq import heappush, heappop
(n, m) = map(int, input().split())
adj = [[] for i in range(n + 1)]
mx_dist = 10 ** 9
dist = [mx_dist] * (51 * (n + 1))
dist[51 * 1] = 0
for i in range(m):
    (u, v, w) = map(int, input().split())
    adj[u].append((v, w))
    adj[v].append((u, w))
h = [(0, 51 * 1)]
while h:
    (d, c) = heappop(h)
    if dist[c] == d:
        (c, last_w) = divmod(c, 51)
        for (ne, w) in adj[c]:
            if last_w:
                new_d = d + (w + last_w) ** 2
                if dist[51 * ne] > new_d:
                    dist[51 * ne] = new_d
                    heappush(h, (new_d, 51 * ne))
            elif dist[51 * ne + w] > d:
                dist[51 * ne + w] = d
                heappush(h, (d, 51 * ne + w))
sys.stdout.write(' '.join([str(dist[51 * i]) if dist[51 * i] != mx_dist else '-1' for i in range(1, n + 1)]))

Solution (Python):
import sys
input = sys.stdin.buffer.readline
from heapq import heappush, heappop
(n, m) = map(int, input().split())
adj = [[] for i in range(n + 1)]
mx_dist = 10 ** 9
dist = [mx_dist] * (51 * (n + 1))
dist[51 * 1] = 0
for i in range(m):
    (u, v, w) = map(int, input().split())
    adj[u].append((v, w))
    adj[v].append((u, w))
h = [(0, 51 * 1)]
while h:
    (d, c) = heappop(h)
    if dist[c] == d:
        (c, last_w) = divmod(c, 51)
        for (ne, w) in adj[c]:
            if last_w:
                new_d = d + (w + last_w) ** 2
                if dist[51 * ne] > new_d:
                    dist[51 * ne] = new_d
                    heappush(h, (new_d, 51 * ne))
            elif dist[51 * ne + w] > d:
                dist[51 * ne + w] = d
                heappush(h, (d, 51 * ne + w))
sys.stdout.write(' '.join([str(dist[51 * i]) if dist[51 * i] != mx_dist else '-1' for i in range(1, n + 1)]))