HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > IMPC16 Group Contests > problem:


24. 50876 - He is my cousin

IMPC16 Group Contests

Start: Jan.16.2016 at 10:00:00 AM
Finish: Jan.16.2016 at 02:00:00 PM
The contest is finished!
• Contest scoreboard

Guest
• Review clarifications (2)

Contest problems

• 11. 50859 - Low performance
• 12. 50860 - Number of Student Certi...
• 13. 50861 - The largest Student Group
• 14. 50862 - Sum of the Pairs
• 15. 50863 - Total Access Cost of a BST
• 21. 50873 - Max Frequency
• 22. 50874 - Apartment Building Adm...
• 23. 50875 - Take m-out
• 24. 50876 - He is my cousin
• 25. 50877 - Friendly Queue
• 32. 50926 - School Mail Merge
• 33. 50927 - Health Expenses
• 34. 50928 - War Of Battleships
• 35. 50929 - Present from your uncles
• F1. 50841 - My grand-grand-grandfa...
• F2. 50936 - Saving the Soldiers
• F4. 50977 - Gaussian Elimination

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 1Person 2Degree of Rel.
853
41Unknown
733
744
So, the total minimum relationship is 10.



Для отправки решений необходимо выполнить вход.

www.contester.ru