Cheapest Routes X81287

We have collected abundant information about the local roads and accommodations in a region that we will traverse. Our plan is to go from city A to city B and we would like to spend the least possible money. For each road connecting two cities u and v we know the cost ω(u,v)=ω(v,u) to travel along that road (tolls, fuel, meals during the journey, …). Every time we go from a city u to one of its neighbors v we must stop at v and spend there one night; we know the cost ω′(v) of stopping at each city v (the cost added by A and B to our route is 0, since they are our initial and final points). All costs, of vertices and of edges, are non-negative. Thus the cost of the route

is

Write a program in C++ which, given an undirected weighted graph with non-negative costs at the vertices and at the edges, and two vertices A and B, returns the cost of the cheapest route to go from A to B, or an indication that not such route exists.

Input All data in the input are non-negative integers. The input starts with two integers 2≤n≤10000 and m, 0≤m≤20n. After that, a sequence of non-negative integers ω′(0), …, ω′(n−1) of the weights ω′(u) of the n vertices of the graph. Then the input contains a sequence of the m edges in the graph as triplets of the form ⟨u,v,ω(u,v)⟩. Vertices u and v are integers in {0,…,n−1} and the weights ω(u,v) are non-negative integers. You can assume that there are no two different edges connecting the same pair of vertices nor any edge connecting a vertex to itself. Finally, there is a sequence of pairs ⟨A_i, B_i⟩, with each A_i and B_i denoting vertices of the graph (0≤A_i,B_i<n).

Output For each pair ⟨A_i, B_i⟩ in the input sequence the program writes the cost δ of the cheapest route between A_i and B_i. with the format c(A_i,B_i) = δ. If no route exists between A_i and B_i the program writes c(A_i,B_i) = +oo. The ouput for each case is ended with a newline (endl).