代写一个算法题，实现太空船的星际跳跃。要求在燃料用完前，在满足黑洞跳跃规则的情况下，使用最小燃料回归。
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:
- 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.
- 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: - It cannot use any wormhole.
- 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.
