Module: Dijkstra's algorithm


Problem

2 /14


Dijkstra

Theory Click to read/hide

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

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!