This is an exercise of an algorithm to find the shortest length of a path on a graph. For a graph with non-negative edge weights, the shortest length of a path on the graph can be found fast with Dijkstra’s algorithm.

In this problem, vertices have weights too, so we cannot directly apply Dijkstra’s algorithm. Instead, we rephrase it into a edge-weighted problem.

When traveling from vertex \(U_i\) to vertex \(V_j\) only via edge \(j\), the cost newly imposed is the cost to use edge \(j\) and to visit vertex \(V_j\), for a total of \(B_j + A_{V_j}\). Conversely, when traveling from vertex \(V_i\) to vertex \(U_j\) only via edge \(j\), the cost newly imposed is the cost to use edge \(j\) and to visit vertex \(U_j\), for a total of \(B_j + A_{U_j}\).

Thus, by adding an edge of weight \(B_j + A_{V_j}\) in the direction of \(U_j \to V_j\) and an edge of weight \(B_j + A_{U_j}\) in the direction of \(V_j \to U_j\), every cost can be represented only with edge weights. By applying Dijkstra’s algorithm on this graph and finally adding the weight of the initial point \(A_1\), one can find the answer. The time complexity is \(O(M \log N)\).

Sample code (PyPy)