Mass Relays are a network of artifacts built by an ancient alien species, used by the various civilizations of the galaxy to travel from one star system to another. However, as Commander John Shepard was returning to the Citadel from a mission from a planet at the edge of the galaxy, he suddenly discovered that something had gone wrong with this network ... in addition to allowing spacecraft to instantaneously travel between any two Mass Relays in the galaxy, they were now also sending the spacecraft across time. EDI, his starship's AI, has devoted all her resources to collect data about how far into the future or past one is sent upon using a Mass Relay Link. However, the Normandy's old algorithm for determining which links to use to reach a particular destination has suddenly proven to be useless, as it doesn't take the time jumps into consideration. As EDI is too busy collecting and analyzing raw data to provide precise information, it would be better if you solved the problem.
- Each Mass Relay is identified by a unique number.
- EDI will provide you with the number of your nearest Mass Relay (starting point) and the number of the Mass Relay closest to the Citadel (target).
- Your task is to determine the path that takes the minimum amount of time to travel from the source to the destination.
- EDI will also give you information about the Mass Relay links, in terms of the the source relay number, the destination relay number and the amount of time it takes to traverse the link from the source to the destination.
- You may assume it takes no time to jump from one link to the next.
- If information about a link is not available, it means that it is not possible to travel directly from the source to the destination.
- Each input case consists of 5 lines.
- The first line will contain two numbers: the source and destination relay numbers.
- The next three lines will consist of N integers each, separated by single spaces, with the N unspecified. Assuming the integers in the 2nd line to be stored in an array A, those in the 3rd line stored in array B, and those in the 4th line stored in array C, the meaning is that it takes C[i] seconds to travel from A[i] to B[i].
- The last line will always be empty.
- N<1000; A[i], B[i], C[i] are 32-bit integers.
- For each test case, print out a single line as defined below.
- In case it is possible to have reach the target but travel indefinitely into the past, print out the string "bigbang" (without quotes) as a warning.
- In case it is not possible to reach the target from the source, print out the string "bigcrunch" (without quotes) as a warning.
- Otherwise, print the minimum time taken to reach the target, followed by the sequence of numbers that specify the order in which mass relays are to be visited.
- In case there are multiple sequences that satisfy the above, print the one with the smaller relay numbers appearing early in the sequence.
1 1 3 2
2 3 4 4
1 1 1 1
1 2 3 2
2 3 2 4
1 1 -2 1
2 1 2 4
Problem Setter: Kaustubh Karkare