Answered

Get the answers you need at Westonci.ca, where our expert community is always ready to help with accurate information. Our platform connects you with professionals ready to provide precise answers to all your questions in various areas of expertise. Explore comprehensive solutions to your questions from a wide range of professionals on our user-friendly platform.

You have just arrived in a new city and would like to see its sights. Each sight is located in a square and you have assigned each a beauty value. Each road to a square takes an amount of time to travel, and you have limited time for sightseeing. Determine the maximum value of beauty that you can visit during your time in the city. Start and finish at your hotel, the location of sight zero.

Sagot :

Answer:

Output

43

Explanation : 0 -> 3 -> 0

Explanation:

Constraints

1 <= n <= 1000

1 <= m <= 2000

10 <= max_t <= 100

0 <= u[i], v[i] <= n-1

u[i] != v[i]

10 <= t[i] <= 100

0 <= beauty[i] <= 10^8

No more than 4 roads connect a single square with others

Two roads can be connected by at most 1 road

Example

n = 4

m = 3

max_t = 30

beauty = [5, 10, 15, 20]

u = [0, 1, 0]

v = [1, 2, 3]

t = [6, 7, 10]

Output

43

Explanation : 0 -> 3 -> 0

We appreciate your time on our site. Don't hesitate to return whenever you have more questions or need further clarification. We hope our answers were useful. Return anytime for more information and answers to any other questions you have. We're glad you visited Westonci.ca. Return anytime for updated answers from our knowledgeable team.