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** (**1** ≤ **n** ≤ **100**, **1** ≤ **s**, **f** ≤ **n**), 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.

Input example #1

3 1 2 0 -1 2 3 0 -1 -1 4 0

Output example #1

6