Background Mr. Panda has started a new delivery company called Amazin which helps customers deliver pack- ages across very long distances. The company houses all its packages inside a warehouse where they are arranged neatly so that they can be located for delivery later. a so that they can be located for dele As the company grows, the number of packages it needs to manage in its warehouse has increased significantly and the human workers simply cannot keep up with the workload. Thus, the company has resorted to using automated robots to help them perform tasks around the warehouse There are many different tasks to be done around the warehouse and efficiency is of utmost impor- tance in order to ensure the packages get delivered on time. Thus, Mr. Panda has hired you, his best programmer, to design and program the most efficient algorithms into the robots to perform several tasks around the warehouse. The warehouse contains N charging points labelled 1 to N. These charging points can charge the robots almost instantly. Using this charging points as vertices, the warehouse can be modelled as an undirected, weighted graph with E edges between the charging points with weight equal to the amount of time taken to travel between them. Some pairs of charging points have no edge because of obstacles such as walls between them The storage unit is at charging point 1 and delivery unit is at charging point N. You need to find a route for the robots to follow to transfer packages from storage to delivery. When following the route, the battery of the robot must be able to last at least as long as the highest weight edge along the path, since that is the maximum amount of time it has to travel without charging. You know you want the route to take at most T time units in total and charging time is negli- gible, however you do not need to choose the shortest path. Instead, you want to save costs by minimising how long the battery needs to last, since longer-lasting batteries are more expensive Design an algorithm and write a program to calculate this minimum value. Input The first line of input will contain 3 integers, N, E and T as described above. The next E ines of input will each contain 3 integers, u, v and w representing an edge between vertices u and v with weight w. The edges in the input will be sorted in non-decreasing weight and the shortest path from 1 to N will be at most T' time units Output Your program simply needs to output one integer on a single line representing how long the battery needs to last in order to deliver the packages within T seconds Example Input 2 6 7 13 1 2 1 5 6 3 3 5 7 Background Mr. Panda has started a new delivery company called Amazin which helps customers deliver pack- ages across very long distances. The company houses all its packages inside a warehouse where they are arranged neatly so that they can be located for delivery later. a so that they can be located for dele As the company grows, the number of packages it needs to manage in its warehouse has increased significantly and the human workers simply cannot keep up with the workload. Thus, the company has resorted to using automated robots to help them perform tasks around the warehouse There are many different tasks to be done around the warehouse and efficiency is of utmost impor- tance in order to ensure the packages get delivered on time. Thus, Mr. Panda has hired you, his best programmer, to design and program the most efficient algorithms into the robots to perform several tasks around the warehouse. The warehouse contains N charging points labelled 1 to N. These charging points can charge the robots almost instantly. Using this charging points as vertices, the warehouse can be modelled as an undirected, weighted graph with E edges between the charging points with weight equal to the amount of time taken to travel between them. Some pairs of charging points have no edge because of obstacles such as walls between them The storage unit is at charging point 1 and delivery unit is at charging point N. You need to find a route for the robots to follow to transfer packages from storage to delivery. When following the route, the battery of the robot must be able to last at least as long as the highest weight edge along the path, since that is the maximum amount of time it has to travel without charging. You know you want the route to take at most T time units in total and charging time is negli- gible, however you do not need to choose the shortest path. Instead, you want to save costs by minimising how long the battery needs to last, since longer-lasting batteries are more expensive Design an algorithm and write a program to calculate this minimum value. Input The first line of input will contain 3 integers, N, E and T as described above. The next E ines of input will each contain 3 integers, u, v and w representing an edge between vertices u and v with weight w. The edges in the input will be sorted in non-decreasing weight and the shortest path from 1 to N will be at most T' time units Output Your program simply needs to output one integer on a single line representing how long the battery needs to last in order to deliver the packages within T seconds Example Input 2 6 7 13 1 2 1 5 6 3 3 5 7
