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! |