Problem A: Ants Colony (Kiến)

ACM ICPC2010 LAR

Kiến xây N tổ theo trật tự mã số 0..N- 1. Khi xây tổ i kiến đào một đường ngầm có độ dài cho trước nối từ tổ đó đến một tổ xây trước. Tổ đầu tiên, số 0, không có đường ngầm nào. Biết rằng từ tổ kiến này có thể đi đến tổ khác thông qua các đường ngầm và qua một vài tổ trung gian. Hãy tìm độ dài ngắn nhất giữa hai tổ kiến.

Input

Gồm nhiều test kết thúc bằng số 0. Mỗi test có cấu trúc như sau:

Dòng đầu tiên: số nguyên dương N là số tổ kiến, 2 £ N £ 10⁵.

Tiếp đến là N-1  dòng, mỗi dòng 2 số nguyên dương A và L. Dòng i, 1 £ i £ N-1 cho biết từ tổ kiến i có đường ngầm dài L đơn vị nối trực tiếp với tổ kiến A, 0 £ A £ i-1, 1 £ L £ 10⁹.

Tiếp đến là Q câu  hỏi, 1 £ Q £ 10⁵, mỗi câu hỏi chiếm 1 dòng gồm 2 số S T, 0 £ S, T £ N-1.

Output

Với mỗi câu hỏi bạn cần ghi ra đường ngắn nhất từ S đến T.  

Thí dụ,

Thuật toán

Tổ chức dữ liệu.

Theo đầu bài, trừ tổ kiến 0, từ mỗi tổ kiến i = 1..N-1 có đúng 1 đường ngầm (2 chiều) nối từ i đến một đỉnh j < i. Ta gọi j là cha trực tiếp của i và gọi mọi tổ kiến nối liên hoàn từ i trở về trước là cha của i. Hai tổ kiến  S và T có đường liên thông khi và chỉ khi S và T có cùng cha k. Bài toán qui về tìm cha chung gần nhất của S và T.

Phần tử cha[i] trỏ đến cha trực tiếp của đỉnh i (mỗi đỉnh là một tổ kiến). Phần tử len[i]  chứa độ dài của đường ngầm từ đỉnh i đến cha trực tiếp của i. Sau khi đọc dữ liệu, với mỗi câu hỏi ta cần tìm đường ngắn nhất từ đỉnh A đến đỉnh B. Gọi K là cha chung gần nhất của A và B. Khi đó có một đường duy nhất từ A đến K và một đường duy nhát từ B đến K, và do đó kiến sẽ bò từ tổ A qua K để đến B. Tổng độ dài của hai đường này sẽ là độ dài ngắn nhất từ A đến B. Độ dài mỗi đường sẽ là tổng các độ dài của đường ngầm trên đường đi.

Chương trình C++

// ANTS.CPP

#include <iostream>

#include <fstream>

using namespace std;

#define Open() ifstream f("ants.inp")

#define Close() f.close()

typedef long long   LL;

const int MN = 100001;

int cha[MN];

LL len[MN];

LL Distance(int s, int t) {

   LL d = 0;            

   while(s != t) {          

      if (s > t) { // chinh s

        d += len[s];

        s = cha[s];

      } else { // chinh t

        d += len[t];

        t = cha[t];

      }

   }

   return d;

}

int Run(){

  int n; // so to kien   

  int i,j;

  int s, t, q; // s,t hai to kien, q so cau hoi

  Open();

  while (1) {

    f >> n;

    cout << "\n\n n = " << n;

    if (n == 0) break;

    for (i = 0; i < n; ++i) cha[i] = i;

    for (i = 1; i < n; ++i) f >> cha[i] >> len[i];

    f >> q; // q cau hoi

    cout << "\n So cau hoi: " << q;

    for (j = 1; j <= q; ++j){

       f >> s >> t;

       cout <<"\n Cau hoi " << j << ": ? "

            << s << " -> " << t << ": ";   

       cout << Distance(s,t);

    } // for j  

  } // while

  Close();

}

main(){

  Run();             

  // ----------------------------

  cout << "\n T H E   E N D.";

  cin.get();

  return 0;      

}