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:
- minimum length of the relationships
- 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 to | Distance |
| 1 | 3 |
| 2 | 5 |
| 3 | 1 |
| 4 | 0 |
| 5 | 2 |
| 6 | 3 |
| 7 | 4 |
| Total | 18 |
| | Table 2
| From person | Total Min Distance |
| 1 | 27 |
| 2 | 19 |
| 3 | 29 |
| 4 |
18 |
| 5 | 53 |
| 6 | 63 |
| 7 | 63 |
|
Для отправки решений необходимо выполнить вход.
|