Module: Dynamic Graph Programming


Problem

5 /7


Shortcut to DAG

Theory Click to read/hide

In solutions using dynamic programming, the order in which the dynamics are calculated is important (it is necessary that the values ​​on which the current one depends are calculated before).
Therefore, if it is necessary to use dynamic programming on directed acyclic graphs, it is necessary to initially construct a topological sorting of the graph. Then calculate the dynamics by sorting through the vertices in the order of the constructed topological sort (depending on the problem, the traversal order can be either from sources to sinks or vice versa).
 
 

Problem

A directed weighted acyclic graph is given. It is required to find the shortest path in it
from vertex s to vertex t.

Input:
The first line of the input file contains four integers n, m, s and t - the number of vertices, edges of the graph, the initial and final vertices, respectively (1 <= n <= 100000; 0 <= m <= 200000; 1 < ;= s, t <= n).
The next m lines contain the descriptions of the edges, one per line. 
Edge number i is described by three integers bi, ei and wi - the beginning, end and length of the edge, respectively (1 <= b i, ei <= n;|wi| <= 1000). 
The graph does not contain cycles and loops.

Output:
The first line of the output file must contain a single integer - the length of the shortest path from s to t. 
If there is no path from s to t, print "Unreachable".

Examples:
 
Input Output
2 1 1 2
1 2 -10 		-10
2 1 2 1
1 2 -10 		Unreachable

time 1500 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!