n places of interest numbered 0 to n − 1; your hotel is at place 0. Place i has beauty beauty[i]. Places are linked by two-way roads: roads[j] = [u, v, t] means travelling between u and v in either direction takes t minutes.
A walk starts and ends at the hotel and lasts at most time_limit minutes. Roads and places may be used any number of times, but each visited place's beauty counts **only once**. The hotel itself counts as visited.
Return the largest total beauty such a walk can collect.beauty=[3, 20, 7, 12], roads=[[0, 1, 15], [1, 2, 10], [0, 2, 25], [0, 3, 30]], time_limit=50 → 30
The loop 0 → 1 → 2 → 0 takes 15 + 10 + 25 = 50 minutes and collects 3 + 20 + 7 = 30. Place 3 is prettier, but the round trip there takes 60 minutes.
beauty=[1, 50, 9], roads=[[0, 2, 10], [1, 2, 40]], time_limit=40 → 10
Place 1 is too far for a round trip, but 0 → 2 → 0 takes 20 minutes and gives 1 + 9 = 10.
beauty=[4, 6], roads=[], time_limit=10 → 4
There are no roads, so the only option is staying at the hotel, worth 4.
beauty=[3, 20, 7, 12], roads=[[0, 1, 15], [1, 2, 10], [0, 2, 25], [0, 3, 30]], time_limit=50
30
Run checks the first 3 tests in your browser. Submit checks all 69 tests on the server, hidden ones included.