Backdoor
InterviewTime limit2sMemory limit512 MB
Find the shortest travel time from junction 0 to junction N-1 in an undirected weighted graph, where every intermediate junction marked visible is blocked and only the Nexus may be entered.
- Level
Medium5 of 10
- Topics
- Shortest path, Graph, Heap, Dynamic programming
- Solved
- No attempts yet
Problem
Yuseop is extremely lazy. Today too, he put off all his work and was playing League of Legends when he realized he has to set a problem by the end of the day. The game had already started, though, and since he hates losing more than anything, he decided to backdoor and finish the game as fast as possible.
He needs to finish the game quickly and set the problem, so he wants to run to the Nexus as fast as he can. Yuseop's champion can be at one of N junctions. Junction 0 is where his champion currently is, junction N-1 is the enemy Nexus, and junctions 1, 2, ..., N-2 are intermediate positions. His champion cannot pass through every junction, however. The point of a backdoor is to move quietly without being spotted, so he cannot pass through any place covered by the enemy's vision: enemy champions, enemy wards (totems that reveal vision), minions, turrets, and so on.
Given whether each junction can be passed through and the time it takes to travel from one junction to another, find the minimum time for Yuseop to get from his current position to the Nexus.
Input
The first line gives two positive integers N and M separated by a space: the number of junctions and the number of paths connecting junctions. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000)
The second line gives N integers a0, a1, ..., a**N-1 separated by spaces, indicating whether each junction is visible to the enemy. If a**i is 0, junction i is not visible to the enemy; if it is 1, it is visible. Additionally, a0 = 0 and a**N-1 = 1. Junction N-1 is the enemy Nexus, so it is unavoidably visible to the enemy, and it is the only visible place that can be entered.
The next M lines each give three integers a, b, t separated by spaces. (0 ≤ a, b < N, a ≠ b, 1 ≤ t ≤ 100,000) This means traveling between junction a and junction b takes t time. Connections are bidirectional, and there is at most one edge between any two junctions.
Output
On the first line, print the minimum time for Yuseop's champion to reach the enemy Nexus without being spotted. If the Nexus cannot be reached, print -1.