## 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.

```3
0 1 0
0 0 1
0 0 0```

### Sample Output

`2`

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

• (0/0)
last test case

• (1/0)
Is the weight always going to be 0 or 1?

• (1/0)
Yes.

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

• (0/0)

• (0/0)
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

• (3/0)
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.

• (0/0)
Thank You!!! :)

• (2/1)
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.