Chocolate and junctions

0

0 votes
Hard, Graphs, Dijkstra's algorithm, Graph Theory, Algorithms, Algorithms, Graph, Shortest path problem, Open, Shortest Path Algorithms
Problem

The city is in the form of a graph and there are N junctions that are connected by M bidirectional roads. The time taken to travel on the ith road is ti. Your house is located at the junction with index s, whereas your storeroom is at junction d. There are several chocolate shops in the city. In the case of any chocolate shortage, shop workers are dispatched from all the police stations immediately.
You are required to determine the least amount of time in which you can reach the storerooms after coming from your house without being intercepted by any staff of chocolate shops at any junction of the city.

Note: Workers can only intercept you at any of the junctions in the city.

Input format

  • First line: A single integer T denoting the number of test cases
  • For each test case:
    • First line: An integer N denoting the number of junctions
    • Second line: N space-separated integers
      Note: If the ith integer is 1, then it means that the ith has chocolate shops. Otherwise, it is 0.
    • Next line: Two integers s and d denoting the junction of the house and the storeroom respectively
    • Next line: Two integers M and 3 denoting the number of roads in your city and the number of columns in the input
    • Next M lines: Three space-separated integers u, v, and t, where u and v are the numbers of the cities connected by this road and t is the time taken to travel on that road
      Note: Input contains self-loops and multiple roads between two junctions.

Output format

For each test case, print a single integer denoting the least amount of time in which you can reach your storeroom avoiding the shop workers. If no such path exists, then print 1.

Constraints

1T10

1N,M105

1s,dN

1u,vN

1t109

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

In the first test case, junctions 1 and 4 have police stations.
MGM Grand is at 2 and safe house at junction 3.
After committing the crime, Danny can reach the safehouse from junction 2 in 3 units of time without being intercepted by the police at any of the junctions.

In the second test case, junction 2 has a police station.
MGM Grand is at junction 2 and safehouse at 1.
Since the police station is at the same junction as MGM Grand police will intercept Danny immediately. Hence, 1.

Editor Image

?