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

Турниры > CEN303_2016Questions > задача:


FE1. 51076 - Key person

CEN303_2016Questions

Старт: 28.окт.2016 в 17:00:00
Финиш: 01.ноя.2016 в 05:00:00
Турнир завершён!
• Турнирная таблица

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

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

• FE1. 51076 - Key person
• FE2. 50988 - Laplacian Filter
• FE3. 51075 - Shortest Path for Bishop
• HW011. 51008 - Sum of Regional M...
• HW012. 51009 - Sum of the nth row
• HW021. 51011 - Decoding the Path
• HW022. 51012 - Palindrome-k
• HW023. 50741 - DNA Distance
• HW031. 51015 - Student Scholarships

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

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

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Question by Ibrahim Mesecan.

Key person

You have a company and you can get/buy friendship information from several internet companies. Now, you want to hire a key person for your company for your business. The key person must have the closest relation with the people that you have defined. The weight of relationships are given to you.

Question: Write a program that will read the relationship information for n people then, it will find the key person for your company.
Notes: 1) The weight/length of relationship from one person to another may have different weights. 2) Assume that length of self-relation is zero and 3) the length of relationship is Max(9999), if one person does not have any connection with somebody else.

Input specification: You will be first given two integers: the number of people and the number of relationships (e). Then in the following e lines, you will be given three integers:
  • the person a: an integer between 1 and n
  • the person b: an integer between 1 and n
  • the length of the relationship: an integer between 1 and Max
where 1 ≤ n ≤ 200 and 0 ≤ e ≤ 10,000.

Output specification: Show two integers:

  1. minimum length of the relationships
  2. the id of the person with the min relationship (If there are several people with the same minimum value, show the one with the biggest id.)

Sample Input
7 12
1 2 2
1 4 5
2 4 1
3 1 2
3 6 2
4 3 1
4 5 2
4 7 5
5 2 10
5 7 2
6 4 8
7 6 2
Sample Output
18 4

Explanation: Minimum relationship length between 4th person and 6th person is 3 (4->3->6). Similarly, minimum relationship length between 4th person and 7th person is 4 (4->5->7). The length of minimum relationships from 4 to all others are given in Table 1 below. The total minimum relationships from all nodes to the other nodes are given in Table 2.

Table 1
Person toDistance
13
25
31
40
52
63
74
Total18
 
Table 2
From personTotal Min Distance
127
219
329
4 18
553
663
763


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

www.contester.ru