HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Graph problems and UF > problem:


51076 - Key person

Guest
• Review clarifications (2)

Section problems

• 50697 - Base Stations
• 50695 - Longest link between neurons
• 50414 - Traffic
• 50698 - Ayran Delivery
• 50978 - Albanian Coders
• 50699 - Fighting Vampires
• 50857 - Nine-Stones Game
• 50929 - Present from your uncles
• 51076 - Key person
• 51080 - Deepest Point
• 51079 - Key person - 2
• 50464 - From Tirana to Durres
• 50691 - The traveling salesman prob...
• 50701 - Cell Removal
• 50703 - The Shortest Path
• 50704 - Connected?
• 50705 - Student Clubs

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.

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