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; }