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 - 2
You have a company and you can get/buy friendship
information from several internet companies. Now, you want
to hire m people who has the greatest number of connections.
If there are people with the same number of
friends/connections, put them in ascending order according
to their total relationship costs and ids.
Question:
Write a program that will read e relationship information for
n people. Then, it will find m people for your company.
Notes:
- The weight/length of relationship
from one person to another is 1 if one knows the other
(if person A knows person B and Person B knows Person C, then
person A knows person C with the length of 2),
- Assume that length of self-relation is zero,
- If person A knows another (B), it does not mean
that person B knows person A (the relationships are directed).
- Assume that if one person does not know another
the distance between them is max (9999),
Input specification:
You will be first given three integers:
- the number of people (n) and
- the number of relationships (e)
- the number of people to show (m)
Then in the following e lines, you will be given
two integers:
- ID of the person a: an integer between 1 and n
- ID of the person b: an integer between 1 and n
which means a knows b; where 1 ≤ m ≤ n ≤ 200
and 0 ≤ e ≤ 10,000.
Output specification:
Show m integers: the IDs (orders) of m people.
| Sample Input |
Sample Output |
7 12 3
1 2
1 4
2 4
3 1
3 6
4 3
4 5
4 7
5 2
5 7
4 6
7 6
|
4 1 2
|
Explanation:
Person 1 knows Persons 2 and 4 directly. But he knows Persons
3, 5, 6, and 7 with a length of 2. So, Person 1 knows 6
people with a total distance of (0+1+2+1+2+2+2=)10. The
table below shows the number of people they know
and the total distance for those people.
| Person ID |
People knows |
Total Distance |
| 4 |
6 | 8 |
| 1 |
6 | 10 |
| 2 |
6 | 12 |
| 3 |
6 | 12 |
| 5 |
6 | 13 |
| 7 |
1 | 1 |
| 6 |
0 | 0 |
Для отправки решений необходимо выполнить вход.
|