USACO OCT08 Problem 'pwalk' Analysis

by Neal Wu

To solve the problem, we find the lengths of the paths for each pair of nodes. We do this recursively by doing a depth-first search (DFS) or iteratively with a queue by doing a breadth-first search (BFS), starting from each node. (For more information, see either the training pages or the following links: DFS BFS.) Note that these searches will always find the paths in linear time for each node because the graph is a tree.

If implemented efficiently, this should take O(N2) time. Afterward, we output the answers to each of the queries one by one for an overall O(N2 + Q) solution. It is also possible to do a single DFS or BFS for each query, resulting in an overall O(NQ) solution that is also fast enough.

The following is a solution that uses BFS:

#include <cstdio>
#include <vector>
using namespace std;

FILE *fout = fopen ("pwalk.out", "w");
FILE *fin = fopen ("pwalk.in", "r");

struct edge
{
    int past, dist;

    edge (int p, int d)
    {
	past = p, dist = d;
    }
};

const int MAXN = 1005;

int N, Q, A, B, L;
vector <edge> adj [MAXN];
int dist [MAXN][MAXN];
int q [MAXN];
int qhead, qtail;

// find the distances to all nodes from num
inline void findpaths (int num)
{
    qhead = qtail = 0;

// initialize queue
    q [qtail++] = num;
    dist [num][num] = 0;

    while (qhead < qtail)
    {
	int top = q [qhead++];

// go through each neighbor
	for (int i = 0; i < (int) adj [top].size (); i++)
	    if (dist [num][top] + adj [top][i].dist < dist [num][adj [top][i].past])
	    {
// update distance and add node to queue
		dist [num][adj [top][i].past] = dist [num][top] + adj [top][i].dist;
		q [qtail++] = adj [top][i].past;
	    }
    }
}

int main ()
{
// initialize to 'infinity'
    memset (dist, 63, sizeof (dist));

// read input
    fscanf (fin, "%d %d", &N, &Q);

    for (int i = 1; i < N; i++)
    {
	fscanf (fin, "%d %d %d", &A, &B, &L);

// use 0-based indexing
	A--, B--;

// add edges
	adj [A].push_back (edge (B, L));
	adj [B].push_back (edge (A, L));
    }

// solve all paths
    for (int i = 0; i < N; i++)
	findpaths (i);

// output
    while (Q--)
    {
	fscanf (fin, "%d %d", &A, &B);
	A--, B--;

	fprintf (fout, "%d\n", dist [A][B]);
    }

    return 0;
}

The following is a solution using DFS:

#include <cstdio>
#include <vector>
using namespace std;

FILE *fout = fopen ("pwalk.out", "w");
FILE *fin = fopen ("pwalk.in", "r");

struct edge
{
    int past, dist;

    edge (int p, int d)
    {
	past = p, dist = d;
    }
};

const int MAXN = 1005;

int N, Q, A, B, L;
vector <edge> adj [MAXN];
int dist [MAXN][MAXN];

// find the lengths of the paths from a certain starting point
void search (int start, int num, int tot)
{
// already found the path, exit
    if (tot >= dist [start][num])
	return;

// set length of path
    dist [start][num] = tot;

// go through all neighbors
    for (int i = 0; i < (int) adj [num].size (); i++)
	search (start, adj [num][i].past, tot + adj [num][i].dist);
}

int main ()
{
// initialize to 'infinity'
    memset (dist, 63, sizeof (dist));

// read input
    fscanf (fin, "%d %d", &N, &Q);

    for (int i = 1; i < N; i++)
    {
	fscanf (fin, "%d %d %d", &A, &B, &L);

// use 0-based indexing
	A--, B--;

// add edges
	adj [A].push_back (edge (B, L));
	adj [B].push_back (edge (A, L));
    }

// solve all paths
    for (int i = 0; i < N; i++)
	search (i, i, 0);

// output
    while (Q--)
    {
	fscanf (fin, "%d %d", &A, &B);
	A--, B--;

	fprintf (fout, "%d\n", dist [A][B]);
    }

    return 0;
}