Dijkstra algorithm
Distance betweeen the vertices
Коль Дейкстрý писать без кучи,
То тайм-лимит ты получишь...
А в совсем другой задаче
Юзай кучу Фибоначчи!
___________________________________________
Спектакль преподавателей ЛКШ.июль-2007
Undirected weighted graph is given. Find the weight of the minimal path between two vertices.
Input
The first line contains two numbers n and m (1 ≤ n ≤ 105
, 1 ≤ m ≤ 2 * 105
) - the number of vertices and edges. Second line contains two numbers s and t (1 ≤ s, t ≤ n, s ≠ t) - the numbers of the vertices the length between which you need to find.
Next m lines contain the description of the edges, one edge in a line. The edge number i is described with three integers bi
, ei
и wi
(1 ≤ bi
, ei
≤ n, 0 ≤ wi
≤ 100) - the vertices connected by the edge and its weight.
Output
Print the weight of the minimal path between the vertices s and t, or -1 if there is no such path.
4 4 1 3 1 2 1 2 3 2 3 4 5 4 1 4
3