ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Турниры > IMPC16 Group Contests > задача:


24. 50876 - He is my cousin

IMPC16 Group Contests

Старт: 16.янв.2016 в 10:00:00
Финиш: 16.янв.2016 в 14:00:00
Турнир завершён!
• Турнирная таблица

Гость
• Вопросы к жюри (2)

Задачи турнира

• 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

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
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