Shortest Path in a Weighted Directed Graph

Given a weighted, directed graph represented as an adjacency matrix, compute the length of the shortest path from a source vertex to a destination vertex using Dijkstra's algorithm. In the matrix, a value of -1 indicates that no direct edge exists between vertices. The distance update follows the formula: \( d[j] = \min(d[j], d[i] + w_{i,j}) \), where \( w_{i,j} \) is the weight from vertex \( i \) to vertex \( j \).

If there is no valid path from the source to the destination, output -1.

inputFormat

The input is given via standard input (stdin) in the following format:

n s t
A[0][0] A[0][1] ... A[0][n-1]
A[1][0] A[1][1] ... A[1][n-1]
...
A[n-1][0] A[n-1][1] ... A[n-1][n-1]

Here, n is the number of vertices, s and t are the source and destination vertices respectively (0-indexed). The next n lines denote the adjacency matrix of the graph. A matrix entry of -1 represents that there is no edge between the corresponding vertices, while any non-negative integer represents the weight of that edge. Self-loops (from a vertex to itself) will always have a value of 0.

outputFormat

Output via standard output (stdout) a single integer which is the length of the shortest path from the source vertex to the destination vertex. If no such path exists, output -1.

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

6