Feedback | | If you notice incorrect translations in Contester, please let author know.
|
|
Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Question by Ibrahim Mesecan.
He is my cousin
Question:
You are given family relationship between n people.
A degree of 1 means that they are first degree relatives,
like father and son, or brother and sister, etc. A degree
of two means the second degree relative: like aunt, uncle,
cousin, etc. If 1 is the first degree relative of 2 and
if 3 is the first degree relative of 2 and
if no other information is provided, 1 is the second
degree relative of 3.
Question: Write a program that
reads the family relationship of n people.
Then, the program finds the min distance between
the given people and shows the total distance.
Input specification
You will be first given three numbers:
- The number of people (n): where 0 ≤ n ≤ 250,
- The number of family relationships (m) given
where 0 ≤ m ≤ 2000,
- The number of family relationships (k) asked
where 0 ≤ k ≤ 100.
The people have the IDs between 1 and n.
The following m lines give three numbers: ID of two people
and the degree of relationship. The following k lines give
two numbers: ID of two people whose relationship is asked.
If there are several relationships between two people, use
the min degree of relationships. For example, your brother is
your uncle's nephew. So, the degree of relationship is 1.
Output specification:
Calculate the total distance of relationships for k
pairs of people. If no relationship is defined between
two people, do not calculate anything for it.
Note: The image on the right is just
for representation. It's not one-to-one related by the example
below.
Sample Input I
8 5 4
3 5 1
3 2 2
3 4 1
3 8 2
2 7 1
8 5
4 1
7 3
7 4
|
Sample Output I
10
|
Explanation: There are 8 people and 6
family relationships are given. Then 4 relationships are asked.
According to the given relationship scheme:
| Person 1 | Person 2 | Degree of Rel. |
| 8 | 5 | 3 |
| 4 | 1 | Unknown |
| 7 | 3 | 3 |
| 7 | 4 | 4 |
So, the total minimum relationship is 10.
Для отправки решений необходимо выполнить вход.
|