A shortest path problem with superheroes and intergalactic journeys
- by Dman
You are a super-hero in the year 2222 and you are faced with this great challenge: starting from your home planet Ilop you must try to reach Acinhet or else your planet will be destroyed by evil green little monsters.
To do this you are given a map of the universe: there are N planets and M inter-planetary connections ( bidirectional ) that bind these planets. Each connection requires a certain time and a certain amount of fuel in order for you to cover the connection from one planet to another.
The total time spent going from one planet to another is obtained by multiplying the time past to cover each connection between all the planets you go through.
There are some "key planets", that allow you to refuel if you arrive on those certain "key planets". A "key planet" is the planet with the property that if it disappears the road between at least two planets would be lost.(In the example posted below with the input/output files such a "key planet" is 2 because without it the road to 7 would be lost)
When you start your mission you are given the possibility of choosing between K ships each with its own maximum fuel capacity.
The goal is to find the SHORTEST TIME CONSUMING path but also choose the ship with the minimum fuel capacity that can cover that shortest path(this means that if more ships can cover the shortest path you choose the one with the minimum fuel capacity). Because the minimum time can be a rather large number (over long long int) you are asked to provide only the last 6 digits of the number.
For a better understanding of the task, here is an example of input/output files:
INPUT: mission.in
7 8 6
1 4
6 5 9 8 7 10
1 2 7 8
1 4 14 9
1 5 3 1
2 3 1 2
2 7 7 1
3 4 2 2
4 6 4 1
5 6 3 7
On the first line (in order): N M K
On the second line :the number for the starting planet and the finishing planet
On the third line :K numbers that represent the capacities of the ships you can choose from
Then you have M lines, all of them have the same structure: Xi Yi Ti Fi-which means that there is a connection between Xi and Yi and you can cover the distance from Xi to Yi in Ti time and with a Fi fuel consumption.
OUTPUT:mission.out
000014 8
1 2 3 4
On the first line:the minimum time and fuel consumption;
On the second line :the path
Restrictions:
2 = N = 1 000
1 = M = 30 000
1 = K = 10 000
Any suggestions or ideas of how this problem might be solved would be most welcomed.
