Python代写:CS314 Galaxy Trek

代写一个算法题,实现太空船的星际跳跃。要求在燃料用完前,在满足黑洞跳跃规则的情况下,使用最小燃料回归。

Requirement

SpaceX has invented a brand-new super-fast spaceship Blue-Triceratops which works with nuclear power and is capable of traveling at intergalactic distances. Currently Blue-Triceratops is orbiting in GRB 090429B which is the farthest known galaxy from us. As you know still it’s not possible to travel faster than speed of light and you may ask how Blue-Triceratops could go that far! The answer is by means of a wormhole named Milky-Shake, which is located in the Milky-Way galaxy! A wormhole has a topological feature that would fundamentally make it a shortcut connecting two separate points in spacetime. Milky-Shake has this capability to send Blue-Triceratops to GRB 090429B in no time but at the cost of decreasing its nuclear fuel by half due to some unknown effect during the transfer. Unfortunately Blue-Triceratops cannot use Milky-Shake again to return back home as wormholes operate only in one direction.

Astrophysicists prepared a map of all known galaxies with all known standard routes between them (i.e. the routes without any threatening objects like black-holes!). Also they have discovered that many of these galaxies contain wormholes which can be used as a shortcut to other galaxies.

Blue-Triceratops starts its journey from GRB 090429B at time 0 with initial fuel amount L. When it traverses a standard route between two galaxies, time increases and fuel decreases by 1 unit. When it traverses a wormhole, time stands still and fuel decreases by a factor of 2. But there is a catch: the wormholes can only be traversed in odd time steps.

More precisely, if Blue-Triceratops arrives at any galaxy in an odd time step, it can do exactly one of the following:

  1. Use any wormhole in the galaxy (if present) to directly jump to the destination of that wormhole in no time, but at the loss of half of its fuel amount.
  2. Use any adjacent standard edge to continue its journey to an adjacent galaxy; this takes unit time and unit fuel (no use of wormhole).

If it arrives at any galaxy at an even time step, then:

  1. It cannot use any wormhole.
  2. It has to use an adjacent standard edge to continue its journey to an adjacent galaxy; this takes unit time and unit fuel.

Also you should know that the spaceship cannot stop anywhere and it should always move forward.

Your mission is to find a path for Blue-Triceratops to return home while consuming the least fuel, or alternatively having the maximum amount of fuel left.

Formally, for simplicity you are given a DAG G=(V,E), where V is the set of galaxies and E is the set of edges which are given in two forms (u,v) or (x,y,*). (u,v) is a simple directed edge between u and v representing a standard route between those two galaxies. (x,y,*) is also a directed edge between galaxies x and y representing a wormhole at x leading to y, which can only be used in an odd time step as discussed above. You should find the optimal path (guaranteed to be unique in test cases) from GRB 090429B to Milky-Way galaxy which results in the minimum fuel consumption.