Problem statement

https://binarysearch.com/problems/Cheapest-Cost-to-All-Cities/

Solution description by @chokn to rework later

First, use Tarjan’s to compress cycles into a new adjacency list. Since all connections between cycles are free, you can use the min to and min from values in the cycle. Make sure you remove the in-connections to 0 from the adjacency, since the path must start at 0.

Second, after constructing new pruned adjacency list, conduct a DFS of each node to find the source nodes in the graph. Since the source nodes connect to all children for free, we only need to build a road to the source node, but can leave from any child node. This means that the out-cost of the source is the min out cost of the children, while the in-cost is the same.

Finally, using this trimmed list of source nodes, use the minimum out-value to connect to all source nodes (except 0) and add the minimal from cost to that node’s to cost. Finally, there’s a small adjustment to make the path start at 0. (res = sources[0] - sources[src]).

Complexity

It is O(E + V) for time and space.

Code

def kosaraju(G, n):
    SCC, S, P, out, D = [], [], [], [0] * n, [0] * n
    st = list(range(n))

    while st:
        x = st.pop()
        if x < 0:
            d = D[~x] - 1
            if P[-1] > d:
                SCC += [S[d:]]
                del S[d:], P[-1]
                for x in SCC[-1]: D[x] = -1
        elif D[x] > 0:
            while P[-1] > D[x]: P.pop()
        elif D[x] == 0:
            S += [x]
            P += [len(S)]
            D[x] = len(S)
            st += [~x]
            st += G[x]

    for x, comp in enumerate(SCC):
        for i in comp: out[i] = x
    return SCC, out


class Solution:
    def solve(self, A, B, edges):
        G, n, INF = defaultdict(list), len(A), float("inf")
        for u, v in edges:
            if v != 0: G[u] += [v]
        T, comps = kosaraju(G, n)

        ### create compressed components and new graph
        A1, B1 = defaultdict(lambda: INF), defaultdict(lambda: INF)
        G2, out_deg = defaultdict(list), Counter()
        for u, v in edges:
            if v == 0: continue
            x, y = comps[u], comps[v]
            if x == y: continue
            G2[x] += [y]
            out_deg[y] += 1

        for i in range(n):
            A1[comps[i]] = min(A1[comps[i]], A[i])
            B1[comps[i]] = min(B1[comps[i]], B[i])
        
        ### create sources
        comp_zero = comps[0]
        sources = {}

        @lru_cache(None)
        def dfs(node):
            ans = A1[node]
            for neib in G2[node]:
                ans = min(ans, dfs(neib))
            if not out_deg[node]: sources[node] = ans
            return ans
        for i in range(len(A1)): dfs(i)

        ### find the shortest connections
        src = min(sources.values())
        ans = sources[comp_zero] - src
        for v in sources:
            if v != comp_zero: ans += src + B1[v]

        return res

Remark

There is always general Edmonds algorithm to find MST in oriented graph.