Graph Contest 3 P1 - Travelling Salesmen

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 32M

Problem type

Some travelling salesmen would like to market their fine wares to N cities in a faraway country.
Salesmen can be found at company offices, which can be found in a select few of these cities.
Now, given that the cities are connected with M roads (and that each bidirectional road takes an hour to traverse) how long will it take for the salesmen to visit every city?

Note: You may assume that there are at least N salesmen at each company office. Also, all cities will be connected to at least one company office.

Input Specification

N \le 1\,000, M \le 100\,000.
Following this will be M lines, each describing a road from city a to city b.
K \le N, the number of company offices.
Following this will be K lines, each with the location of a company office.
Bonus: one case will have N, K \le 30\,000.

Output Specification

The number of hours it will take for news of the product to spread.

Sample Input

4 3
1 2
2 3
3 4

Sample Output


City 4 will be visited last.


  • 4
    Evanhyd  commented on June 6, 2022, 1:29 a.m. edited

    me: Mom, I want to solve a Travelling Salesman problem
    mom: We have a Travelling Salesman problem at home
    Travelling Salesman problem at home: