## CCO '23 P5 - Travelling Trader

View as PDF

Points: 30 (partial)
Time limit: 2.0s
Memory limit: 1G

Author:
Problem types

A trader would like to make a business of travelling between cities, moving goods from one city to another in exchange for a profit. There are cities labelled and roads. Each road joins two cities and takes one day to traverse. It is possible to reach any city from any other city using these roads.

#### Input Specification

The first line of input contains two space-separated integers and .

The next lines of input each contain two space-separated integers and , describing a road.

The last line of input contains integers , the profits given by choosing to do business in the corresponding city.

Marks AwardedBounds on Bounds on
marks
marks
marks
marks
marks
marks

#### Output Specification

On the first line, output the maximum possible total profit.

On the second line, output , the number of cities the trader does business in on an optimal route.

On the third line, output M space-separated integers , the cities the trader does business in on an optimal route in order, starting with .

If there are multiple possible correct outputs, any correct output will be accepted.

#### Sample Input 1

4 1
1 2
1 3
2 4
3 1 4 1

#### Output for Sample Input 1

7
2
1 3

#### Explanation of Output for Sample Input 1

On day , the trader starts by doing business in city , making a profit of .

On day , the trader moves to city and does business there, making a profit of .

At this point, the trader cannot reach another city in which they have not done business before getting laid off, so their total profit is .

#### Sample Input 2

5 2
1 2
1 3
2 4
2 5
3 1 4 1 5

#### Output for Sample Input 2

14
5
1 4 5 2 3

#### Explanation of Output for Sample Input 2

The trader can make a profit in every city by visiting them in the order .

Note that the trader strategically delays doing business in city to ensure they do not go more than days without making a profit.