CF1900E Transitive Graph

You are given a directed graph $ G $ with $ n $ vertices and $ m $ edges between them. Initially, graph $ H $ is the same as graph $ G $ . Then you decided to perform the following actions: - If there exists a triple of vertices $ a $ , $ b $ , $ c $ of $ H $ , such that there is an edge from $ a $ to $ b $ and an edge from $ b $ to $ c $ , but there is no edge from $ a $ to $ c $ , add an edge from $ a $ to $ c $ . - Repeat the previous step as long as there are such triples. Note that the number of edges in $ H $ can be up to $ n^2 $ after performing the actions. You also wrote some values on vertices of graph $ H $ . More precisely, vertex $ i $ has the value of $ a_i $ written on it. Consider a simple path consisting of $ k $ distinct vertices with indexes $ v_1, v_2, \ldots, v_k $ . The length of such a path is $ k $ . The value of that path is defined as $ \sum_{i = 1}^k a_{v_i} $ . A simple path is considered the longest if there is no other simple path in the graph with greater length. Among all the longest simple paths in $ H $ , find the one with the smallest value.

N/A

N/A

In the first test case, the longest path in both graphs is $ 1 \to 3 \to 4 \to 5 \to 2 $ . As the path includes all vertices, the minimal possible value of the longest path is the sum of values on all vertices, which is $ 12 $ . In the second test case, the longest possible path is $ 1 \to 2 \to 3 \to 4 \to 6 \to 7 $ . As there are no longest paths with vertex $ 5 $ in them, this path has the minimal possible value of $ 5\,999\,999\,995 $ . In the third test case, it can be proven that there is no path longer than $ 11 $ and that the value of the longest path cannot be less than $ 37 $ . Also, notice that the given graph has both self-loops and multiple edges.