Shortest Path

Given a graph as an adjacency matrix, find the shortest path from the first to the last vertex.

Input

N ≤ 100, the number of vertices.
The adjacency matrix - N rows of N numbers.
The first row represents the first vertex, and similarly the last row = the last vertex.

Output

The distance from the first vertex to the last one.

Sample Input

3
0 1 0
0 0 1
0 0 0

Sample Output

2

All Submissions
Best Solutions


Point Value: 5
Time Limit: 2.00s
Memory Limit: 16M
Added: Jun 28, 2013

Problem Types: [Show]

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Is the weight always going to be 0 or 1?


What does the problem mean? Should the sample print 0 instead of 2? Because it seems that dist[1][3] = 0 so we can directly go from 1 to 3.

Read this first:
http://wcipeg.com/wiki/Graph_theory#Adjacency_matrix

My program solves all test cases in a few milliseconds, but i am always getting that timeline expired error in the last test case and i' m wondering if that is a bug

You're not pruning your depth first search correctly. Lets assume your program does find the shortest path of length 100 from vertex 1 to 100. It will still take a long time traversing all of the possible paths of length 1-99 that may or may not reach vertex 100.

Thank You!!! :)

In general, if other people have solved the problem (there've been 65 in this case!), it probably isn't a problem with the judge.