IOI Crocodile

So I’m doing this problem from the IOI, and I don’t even know where to start. Should I actually try to make the escape plan, or should I just keep track of the costs while running some eldritch form of Dijkstra’s?

I’d appreciate any hint or pointer.