Company: Hushh Ai_15oct
Difficulty: medium
Coins Respawn There is a directed graph with N vertices numbered 1 to N and M edges. The i -th edge is directed from vertex A_i to vertex B_i , and C_i coins are placed along that edge. There is a button on vertex N . You start the game standing on vertex 1 with zero coins and head for vertex N by traversing edges and collecting coins. Traversing one edge takes exactly one minute. Every time you traverse an edge you collect the coins placed along it. The coins respawn immediately, so traversing the same edge again collects the same number of coins again. You may traverse edges in any order, revisit vertices, and reuse edges as often as you like. Whenever you are standing on vertex N you may press the button to end the game. You may also leave vertex N without pressing the button and keep travelling. When you end the game after T minutes you are asked to pay T P coins. If you hold fewer than T P coins you pay everything you hold instead. Your score is the number of coins you still hold