Computer Science Canada DWITE Round 2 #4  | 
  
| Author: | A.J [ Thu Nov 26, 2009 7:21 pm ] | ||
| Post subject: | DWITE Round 2 #4 | ||
I noticed that a lot of people implemented Floyd-Warshall for this question. However, according to me at least, there exists a nicer solution: 
 The basic idea is that if 2 points A and B are connected, and if dist[B] < dist[A] + 1, store dist[A] + 1 in dist[B] (where dist[x] contains distance from 1, and dist[1] = 0, and dist[x] = 999999 for all other values of x). O(n^2) as opposed to Floyd-Warshall's O(n^3). This solution was taken from the team 'Zaiphyr' from Waterloo Collegiate Institute, and all credit goes to Yusong Men (founder of the aforementioned team).  | 
	|||
| Author: | yusong [ Fri Nov 27, 2009 2:24 pm ] | 
| Post subject: | RE:DWITE Round 2 #4 | 
Nice, Thank You AJ!  | 
	|