EN
RU
ES
ZH
FR
DE
PT
AR
HI
Searching for the shortest path in a graph using classes
PHP
Hard
classes
Task «Searching for the shortest path in a graph using classes»
Implement the Graph class to represent a weighted directed graph. The class must contain the methods addEdge(int $from, int $to, int $weight) for adding an edge and shortestPath(int $start, int $end) for finding the shortest path from vertex $start to $end using Dijkstra's algorithm. If no path exists, the method should return -1. It is guaranteed that edge weights are positive, the number of vertices does not exceed 1000, and the number of edges is up to 10000.
Input Format
In the first line, N (number of vertices) and M (number of edges) are given separated by a space. Then, in M lines, the edges are given: from to weight. In the last line, start and end are given.
Output Format
An integer — the minimum cost of the path from start to end, or -1 if there is no path.
Examples
Example 1
INPUT
10
OUTPUT
87
Example 2
INPUT
3 2
1 2 5
2 3 10
1 3
OUTPUT
15
Example 3
INPUT
1
OUTPUT
0
Example 4
INPUT
2 1
1 2 7
2 1
OUTPUT
-1
main.php