Answered

Welcome to Westonci.ca, where finding answers to your questions is made simple by our community of experts. Connect with a community of professionals ready to provide precise solutions to your questions quickly and accurately. Get detailed and accurate answers to your questions from a dedicated community of experts on our Q&A 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 hope you found what you were looking for. Feel free to revisit us for more answers and updated information. We hope our answers were useful. Return anytime for more information and answers to any other questions you have. Stay curious and keep coming back to Westonci.ca for answers to all your burning questions.