P10166 [DTCPC 2024] Cycle.

Cycle.

Given a directed graph $G$ with no multiple edges and no self-loops, and a sequence $\{a_n\}$, each time you may add a directed edge $i\to j$ at a cost of $a_i+a_j$. Find the minimum total cost to make it possible to find $k\geq 2$ distinct vertices $p_1,p_2,\dots,p_k$ such that for all $i\in [1,k]$, there is an edge $p_i\to p_{i\bmod k+1}$.

The first line contains two integers $n,m$ ($2\le n\le 5 \times 10^5$, $n-1 \le m \le 10^6$), denoting the number of vertices and edges in the graph. The second line contains $n$ integers, denoting the sequence $\{a_n\}$ ($1\le a_i\le 10^9$). The next $m$ lines each contain two integers $u,v$ ($1\le u,v\le n$), meaning there is a directed edge $u\to v$.

Output one integer in a single line, denoting the minimum cost.

Translated by ChatGPT 5