TomTom Cruise
Time limit1sMemory limit1024 MB
Find a simple path with at least one edge in a weighted graph that minimizes the sum of its edges plus the vertex weights of both endpoints.
- Level
Medium7 of 10
- Topics
- Graph, Shortest path, Dynamic programming, Greedy
- Solved
- No attempts yet
Problem
You intend to take a trip from your base to Ganymede. You have a spaceship which you will use for the whole trip. It will take some fuel to get there, some fuel to traverse part of the moon, and some fuel to get back to the base.
There are some points on Ganymede you can visit. The map of Ganymede is given as a graph where the weight of each vertex is equal to the amount of fuel it will take to traverse between the corresponding point and your base. The weight of each edge equals to the amount of fuel it will take to traverse between vertices which are connected by the edge, in either direction. In order for your trip to be reasonable, you do not want to visit any edge or any vertex twice. However, you have to traverse at least one edge.
What is the least amount of fuel you will need to accomplish such a trip?
Input
First line of the input contains two integers N and M, the number of vertices and edges, respectively (1 ≤ N ≤ 10^4, 0 ≤ M ≤ min(N(N-1)/2, 2 · 10^4)). Next line contains N integers v_0, v_1, ..., v_{N-1} (1 ≤ v_i ≤ 10^6), weights of respective vertices 0, 1, ..., N-1. Each of the next M lines contains three integers f_i, t_i, and w_i (0 ≤ f_i, t_i < N, 1 ≤ w_i ≤ 10^6), the two vertices connected by the edge and the edge weight, respectively.
Output
Output the minimum amount of fuel you have to spend on your trip.