Agamemnon, the great king of Mycenae, was assembling his troops in Aulis to sail to the shores of Troy, when he had a vision of goddess Artemis. In this vision, Agamemnon found out that he had accid
Agamemnon, the great king of Mycenae, was assembling his troops in Aulis to sail to the shores of Troy, when he had a vision of goddess Artemis. In this vision, Agamemnon found out that he had accidentally slain a deer that was sacred to Artemis, and now the goddess swore to make Agamemnon suffer on his voyage to Troy. Along his route to Troy, Agamemnon was planning to stop at the islands of Crete to gather resources for his formidable army. If Artemis were to find out about the sea routes Agamemnon took, she would use her powers to stop the wind along those routes, leaving Agamemnon and his crew stranded. As the trusty advisor of Agamemnon, you now have to help him devise a path between the islands of Crete that provides the army the maximum amount of resources, without letting Artemis discover the routes you take. The NNN islands of Crete are connected to each other via N−1N − 1N−1 sea routes. Along each route, Agamemnon can acquire a certain amount of resources. However, if a route is used more than kkk times, Artemis will detect the presence of Agamemnon along that route and stop the wind along that route. So, a feasible plan cannot use any route more than kkk times. Given that Agamemnon can start and end at any of the islands of Crete, come up with a feasible plan that maximises Agamemnon’s resource earnings. Note that Agamemnon can only collect resources along a sea route during its first use. He does not earn extra resources from a route on reusing it.
