Module: Dijkstra's algorithm


Problem

2 /14


Dijkstra

Problem

You are given a directed weighted graph. Find the shortest distance from one given vertex to another.
 
Input
The first line contains three numbers: N, S and F (1≤ N≤ 100, 1≤ S, F≤ N), where N – number of graph vertices, S – initial vertex, and F – final. In the next N lines, enter N numbers each, not exceeding 100, – graph adjacency matrix, where -1 means no edge between vertices, and any non-negative number – the presence of an edge of given weight. Zeros are written on the main diagonal of the matrix.
Output
It is required to display the desired distance or -1 if there is no path between the specified vertices.

Examples
# Input Output
1
3 2 1
0 1 1
4 0 1
2 1 0
3