**Analysis: Cross Country Skiing by Fatih Gelgi and Brian Dean**

Suppose we have a function `Reachable(X)` that tells us (i.e. returns
true) if all waypoints are reachable with absolute elevation difference at most
X. Then by calling `Reachable` with different X values we can find D.
Obviously, we cannot try all X values since X is in the range 0..1,000,000,000.
Remember that we're looking for the minimum value of D which means we can use
binary search:

Dmin=0, Dmax=1000000000 while Dmin < Dmax X = (Dmin + Dmax) / 2 if Reachable(X) Dmax = X else Dmin = X + 1 D = Dmin

Now we can work on a `Reachable` function which implements floodfill
algorithm: starting from one waypoint, continue expanding cells while elevation
difference is D between adjacent cells. As you know, we can use either Depth
First Search (DFS) or Breath First Search (BFS) for floodfill. However, this is
a little tricky since DFS may fail on some of the inputs. The depth of
recursion can go up to NM which is too deep. On the other hand, using BFS will
be safe.

For each `Reachable` function call, O(NM) time is required. Since
binary search calls the function O(log R) times (where R is the range
0..1,000,000,000), the total running time is O(MN log R). Here is a sample
code:

#include <fstream> #include <cmath> #include <queue> #define MAX 501 using namespace std; const int dy[]={-1,0,1,0},dx[]={0,-1,0,1}; int m,n,mat[MAX][MAX],wp[MAX][MAX],mark[MAX][MAX],wy,wx; // floodfill with BFS within elevation difference d void floodfill(int d) { queue<pair<int,int> > q; q.push(make_pair(wy,wx)); mark[wy][wx]=1; while (!q.empty()) { pair<int,int> p=q.front(); q.pop(); for (int i=0; i<4; i++) { int ny=p.first+dy[i],nx=p.second+dx[i]; if (ny>=0 && ny<m && nx>=0 && nx<n) // if the target cell is not visited before // and the elevation difference is within D // push the cell into the queue if (!mark[ny][nx] && abs(mat[p.first][p.second]-mat[ny][nx])<=d) { q.push(make_pair(ny,nx)); mark[ny][nx]=1; } } } } // check if all waypoints are reachable with elevation difference D bool reachable(int d) { // reset the grid that keeps the reachable points for (int i=0; i<m; i++) for (int j=0; j<n; j++) mark[i][j]=0; floodfill(d); // check if there is any unreachable waypoints for (int i=0; i<m; i++) for (int j=0; j<n; j++) if (wp[i][j] && !mark[i][j]) return false; return true; } int main() { ifstream fin("ccski.in"); fin >> m >> n; for (int i=0; i<m; i++) for (int j=0; j<n; j++) fin >> mat[i][j]; for (int i=0; i<m; i++) for (int j=0; j<n; j++) { fin >> wp[i][j]; // keep one of the waypoints as the starting point if (wp[i][j]) wy=i,wx=j; } fin.close(); // binary search int dmin=0,dmax=1000000000; while (dmin<dmax) { int d=(dmin+dmax)/2; if (reachable(d)) dmax=d; else dmin=d+1; } ofstream fout("ccski.out"); fout << dmin << "\n"; fout.close(); }

In addition to being solvable by a floodfill wrapped inside a binary search, this problem also has a nice solution using ideas from minimum spanning trees. Whereas a standard shortest path between two nodes in a graph minimizes the sum of the edge weights along the path, a so-called "bottleneck" shortest path minimizes the largest edge weight along the path. One can compute bottleneck shortest paths using a variant of Dijkstra's algorithm (which is actually the same as the minimum spanning tree algorithm of Prim/Jarnik). Moreover, a nice property of minimum spanning trees is that the unique path through an MST between any two nodes is actually a bottleneck shortest path; hence, computing a minimum spanning tree effectively computes bottleneck shortest paths between all pairs of nodes.

Armed with the insight above, we can now solve this problem by computing a minimum spanning tree, say by using Kruskal's well-known algorithm that adds edges in sorted order. We first pre-sort all the edges (differences between adjacent cells) and then add them one by one to our MST. The only difference is that instead of running this process to completion to build a full MST, we stop at the moment when our partial MST contains all the waypoints. The last edge weight we added will give us the value of D we seek, since we need at least this value of D to connect all the waypoints together. The running time for this approach would be the same as that of Kruskal's algorithm, which is dominated by the time required to sort the edges: O(MN log MN).