#857. JUMPING - Khỉ con học nhảy

Có một chú khỉ con đang học nhảy từ cành nọ sang cành kia tại cái cây chú ưa thích. Cây có đỉnh được đánh số từ đến , có cạnh và chú có thể nhảy giữa các đỉnh có khoảng cách không quá (khoảng cách được tính là số cạnh trên đường đi ngắn nhất giữa hai đỉnh).

Gọi là số bước nhảy ít nhất để chú nhảy từ đỉnh đến đỉnh . Hãy tính giá trị biểu thức:

Dữ liệu vào:

• Dòng đầu tiên có hai số và ;
• Dòng tiếp theo có số thể hiện có đường đi từ đỉnh đến với ( thì đỉnh là gốc cây).

Dữ liệu ra:

• Một số nguyên duy nhất là đáp số bài toán.

Ví dụ:

Dữ liệu vào:

6 2
0 1 1 2 2 4

Dữ liệu ra:

20

Dữ liệu vào:

14 5
0 1 1 1 2 2 3 4 4 4 5 5 7 7

Dữ liệu ra:

95