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)

TheBoss77 on Feb 22, 2020 - 2:54:26 am UTC help
  • (0/0)
last test case

Chinadoll on Feb 17, 2017 - 9:25:52 pm UTC weight?
  • (1/0)
Is the weight always going to be 0 or 1?


4Dmovie on Nov 24, 2016 - 5:02:21 pm UTC
  • (0/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.

Kirito on Nov 25, 2016 - 12:50:18 am UTC Re: ...
  • (0/0)
Read this first:
http://wcipeg.com/wiki/Graph_theory#Adjacency_matrix

Guru_Charis on Apr 15, 2015 - 4:32:09 pm UTC
  • (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

wgma00 on Apr 16, 2015 - 4:56:26 am UTC Re: ...
  • (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.

Guru_Charis on Apr 16, 2015 - 10:05:03 am UTC Re: ...
  • (0/0)
Thank You!!! :)

jargon on Apr 17, 2015 - 3:15:40 am UTC Re: ...
  • (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.