Company: Rippling_4april
Difficulty: medium
Question 1 You have just arrived in a new city and want to see its attractions. Each sight has an assigned beauty value and each road between sights takes a certain amount of time to travel. You have a limited amount of time for sightseeing and must start and finish at your hotel, located at sight zero. Determine the maximum value of beauty that you can visit during your time in the city. Example n = 4 m = 3 max_t = 50 beauty = [5, 10, 15, 20] u = [0, 1, 0] v = [1, 2, 3] t = [10, 10, 10] n = 4 sights are chosen in the map, including the hotel at sight 0. m = 3 bidirectional roads that connect them Edges are between sights u[i] and v[i] , and t = t[i] is the time to travel edge i . beauty = [5, 10, 15, 20] represents the beauty values for sights 0, 1, 2, and 3, respectively. To visit sight 0, 1 and 2 (Starting at the hotel and ending at the hotel), it takes 10 + 10 + 10 + 10 = 40 minutes, and it has 5 + 10 + 15 = 30 beauty value (the beauty value is counted only on your first visit.) To