e-olymp
Competitions

ADA University - February 3 - Dijkstra

Dijkstra Algorithm

The directed weighted graph is given. Find the shortest path from the vertex s to the vertex f.

Input

The first line contains three numbers n, s and f (1n100, 1s, fn), where n is the number of vertices in a graph. Each of the next n lines contains n numbers - the adjacency matrix of the graph, where the number in the i-th line and j-th column corresponds to the edge from i to j: -1 means the absence of the edge between the vertices, and any non-negative number - the presence of the edge of a given weight. The main diagonal of the matrix contains always zeroes.

Output

Print the required distance or -1 if the path between the given vertices does not exist.

Time limit 1 second
Memory limit 128 MiB
Input example #1
3 1 2
0 -1 2
3 0 -1
-1 4 0
Output example #1
6