Graph Contest 3 P1 - Travelling Salesmen - Olympiads Online Judge

Graph Contest 3 P1 - Travelling Salesmen

View as PDF

Submit solution

All submissions

Best submissions

Points: 7

Time limit: 1.0s

Memory limit: 32M

Problem type

Some travelling salesmen would like to market their fine wares to $N$ ~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$ ~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$ ~N~ salesmen at each company office. Also, all cities will be connected to at least one company office.

Input Specification

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

Output Specification

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

Sample Input

Sample Output

City 4 will be visited last.

Comments

11

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: