Minimum Travel Time Avoiding Flooded Roads

You are given a directed graph with n intersections and m streets. Each street is described by three integers u, v and t which indicate that there is a road from intersection u to intersection v taking t time.

In addition, there are k flooded road segments specified as pairs (p, q). Any street from intersection p to intersection q that appears in the flooded list should be avoided when traveling.

Your task is to compute the minimum travel time from a given start intersection s to a destination intersection d. If there is no valid path that avoids all flooded roads, output \(-1\).

The problem can be formulated using Dijkstra's algorithm with the twist of ignoring the banned edges. In LaTeX format, the problem is: Find the minimum time \(T\) such that if there exists a path \(P = (s = v_0, v_1, ..., v_k = d)\) with total time \(\sum_{i=0}^{k-1} t(v_i, v_{i+1}) = T\) and for no edge \((v_i,v_{i+1})\) in \(P\) it holds that \((v_i,v_{i+1}) \in B\) (where \(B\) is the set of flooded roads), then output \(T\); otherwise, output \(-1\).

inputFormat

The input is read from standard input in the following format:

• The first line contains five integers: \(n\), \(m\), \(k\), \(s\), and \(d\), where \(n\) is the number of intersections, \(m\) is the number of streets, \(k\) is the number of flooded road segments, \(s\) is the start intersection, and \(d\) is the destination intersection.
• The next \(m\) lines each contain three integers \(u\), \(v\), and \(t\), representing a street from intersection \(u\) to \(v\) with travel time \(t\).
• The following \(k\) lines each contain two integers \(p\) and \(q\), indicating a flooded road segment from intersection \(p\) to \(q\) that must be avoided.

Note that intersections are numbered from 1 to \(n\).

outputFormat

Output a single integer to standard output which is the minimum travel time from intersection \(s\) to intersection \(d\) avoiding all the flooded roads. If there is no valid path, output \(-1\).

5 7 2 1 5
1 2 4
1 3 2
2 4 5
3 4 8
3 5 10
4 5 2
5 4 9
2 3
4 5

12