Travelling SalesmenSome travelling salesmen would like to market their fine wares to several 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 many roads (and that each bidirectional road takes an hour to traverse) how long will it take for the salesmen to visit every city?
InputN ≤ 1,000, M ≤ 100,000.
Following this will be M lines, each describing a road from city a to city b.
K ≤ 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 ≤ 30,000.
OutputThe number of hours it will take for news of the product to spread.
4 3 1 2 2 3 3 4 2 1 2
City #4 will be visited last.
Point Value: 10
Time Limit: 2.00s
Memory Limit: 32M
Added: Mar 04, 2009
- Graph Theory
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3