-----------------------------------

A.J

Thu Nov 26, 2009 7:21 pm


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:


#include
using namespace std;
int n, x, y, ans, num

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


-----------------------------------

yusong

Fri Nov 27, 2009 2:24 pm


RE:DWITE Round 2 #4

-----------------------------------

Nice, Thank You AJ!