Weights Distributing (Codeforces 1343E)
Tags: Greedy, shortest paths

You are given an undirected unweighted graph consisting of $$$n$$$ vertices and $$$m$$$ edges (which represents the map of Bertown) and the array of prices $$$p$$$ of length $$$m$$$. It is guaranteed that there is a path between each pair of vertices (districts).Mike has planned a trip from the vertex (district) $$$a$$$ to the vertex (district) $$$b$$$ and then from the vertex (district) $$$b$$$ to the vertex (district) $$$c$$$. He can visit the same district twice or more. But there is one issue: authorities of the city want to set a price for using the road so if someone goes along the road then he should pay the price corresponding to this road (he pays each time he goes along the road). The list of prices that will be used $$$p$$$ is ready and they just want to distribute it between all roads in the town in such a way that each price from the array corresponds to exactly one road.You are a good friend of Mike (and suddenly a mayor of Bertown) and want to help him to make his trip as cheap as possible. So, your task is to distribute prices between roads in such a way that if Mike chooses the optimal path then the price of the trip is the minimum possible. Note that you cannot rearrange prices after the start of the trip.You have to answer $$$t$$$ independent test cases.

Input: The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.The first line of the test case contains five integers $$$n, m, a, b$$$ and $$$c$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$n-1 \le m \le min(\frac{n(n-1)}{2}, 2 \cdot 10^5)$$$, $$$1 \le a, b, c \le n$$$) — the number of vertices, the number of edges and districts in Mike's trip.The second line of the test case contains $$$m$$$ integers $$$p_1, p_2, \dots, p_m$$$ ($$$1 \le p_i \le 10^9$$$), where $$$p_i$$$ is the $$$i$$$-th price from the array.The following $$$m$$$ lines of the test case denote edges: edge $$$i$$$ is represented by a pair of integers $$$v_i$$$, $$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$, $$$u_i \ne v_i$$$), which are the indices of vertices connected by the edge. There are no loops or multiple edges in the given graph, i. e. for each pair ($$$v_i, u_i$$$) there are no other pairs ($$$v_i, u_i$$$) or ($$$u_i, v_i$$$) in the array of edges, and for each pair $$$(v_i, u_i)$$$ the condition $$$v_i \ne u_i$$$ is satisfied. It is guaranteed that the given graph is connected.It is guaranteed that the sum of $$$n$$$ (as well as the sum of $$$m$$$) does not exceed $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$, $$$\sum m \le 2 \cdot 10^5$$$).

Output: For each test case, print the answer — the minimum possible price of Mike's trip if you distribute prices between edges optimally.

Note: One of the possible solution to the first test case of the example:One of the possible solution to the second test case of the example:

Sample Inputs:
2
4 3 2 3 4
1 2 3
1 2
1 3
1 4
7 9 1 5 7
2 10 4 8 5 6 7 3 3
1 2
1 3
1 4
3 2
3 5
4 2
5 6
1 7
6 7

Sample Outputs:
7
12

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
    return int(sys.stdin.readline())

def MI():
    return map(int, sys.stdin.readline().split())

def MI1():
    return map(int1, sys.stdin.readline().split())

def LI():
    return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
    return [LI() for _ in range(rows_number)]

def SI():
    return sys.stdin.readline()[:-1]

def main():

    def bfs(u):
        q = deque([u])
        res = [-1] * n
        res[u] = 0
        while q:
            u = q.popleft()
            for v in to[u]:
                if res[v] != -1:
                    continue
                res[v] = res[u] + 1
                q.append(v)
        return res
    for _ in range(II()):
        (n, m, a, b, c) = MI()
        (a, b, c) = (a - 1, b - 1, c - 1)
        pp = LI()
        to = [[] for _ in range(n)]
        for _ in range(m):
            (u, v) = MI1()
            to[u].append(v)
            to[v].append(u)
        dist = []
        for u in [a, b, c]:
            dist.append(bfs(u))
        cs = [0]
        for p in sorted(pp):
            cs.append(cs[-1] + p)
        ans = 10 ** 16
        for u in range(n):
            d = dist[0][u] + dist[1][u] + dist[2][u]
            if d > m:
                continue
            cur = cs[d] + cs[dist[1][u]]
            if cur < ans:
                ans = cur
        print(ans)
main()

Solution (Python):
import sys
import math
from math import factorial, inf, gcd, sqrt
from heapq import *
from functools import *
from itertools import *
from collections import *
from typing import *
from bisect import *
import random
from sys import stdin, stdout
sys.setrecursionlimit(10 ** 5)

def inp():
    return stdin.readline().strip()

def iinp():
    return int(inp())

def mp():
    return map(int, inp().split())

def lmp():
    return list(mp())

def bfs(g, d, a):
    q = deque()
    q.append(a)
    d[a] = 0
    while q:
        a = q.popleft()
        for i in g[a]:
            if d[i] > d[a] + 1:
                d[i] = d[a] + 1
                q.append(i)
ti = int(input())
for i in range(ti):
    (n, m, a, b, c) = mp()
    val = sorted(lmp())
    g = [[] for i in range(n + 1)]
    for i in range(m):
        (c1, c2) = mp()
        g[c1].append(c2)
        g[c2].append(c1)
    (da, db, dc) = ([inf] * (n + 1), [inf] * (n + 1), [inf] * (n + 1))
    bfs(g, da, a)
    bfs(g, db, b)
    bfs(g, dc, c)
    s = list(accumulate(val, initial=0))
    ans = inf
    if db[a] + db[c] < len(s):
        ans = s[db[a] + db[c]]
    for x in range(1, n + 1):
        if da[x] + dc[x] + db[x] < len(s):
            ans = min(ans, s[db[x]] + s[da[x] + dc[x] + db[x]])
    print(ans)

Solution (Python):
from collections import deque
from sys import stdin, stdout
int1 = lambda x: int(x) - 1

def MI():
    return map(int, stdin.readline().split())

def MI1():
    return map(int1, stdin.readline().split())

def LI():
    return list(map(int, stdin.readline().split()))

def BFS(adj, level, s):
    queue = deque([s])
    level[s] = 0
    while queue:
        s = queue.popleft()
        for i in adj[s]:
            if level[i] == -1:
                queue.append(i)
                level[i] = level[s] + 1
t = int(input())
for _ in range(t):
    (n, m, a, b, c) = MI()
    (a, b, c) = (a - 1, b - 1, c - 1)
    p = LI()
    cost = [0]
    p.sort()
    for x in p:
        cost.append(cost[-1] + x)
    adj = [[] for i in range(n)]
    for i in range(m):
        (u, v) = MI1()
        adj[u].append(v)
        adj[v].append(u)
    (da, db, dc) = ([-1] * n, [-1] * n, [-1] * n)
    BFS(adj, da, a)
    BFS(adj, db, b)
    BFS(adj, dc, c)
    ans = 10 ** 18
    for i in range(n):
        x = da[i] + db[i] + dc[i]
        if x <= m:
            cx = cost[x] + cost[db[i]]
            ans = min(ans, cx)
    stdout.write(str(ans) + '\n')