Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

European Rover Challenge!

By SilentG · Limits 1s, 512 MB

The European Rover Challenge (ERC) Space and Robotics Event is a prestigious space-robotics event combining international competitions of mobile robots with scientific and technological shows. University teams from around the world build their own Martian robots, and then take part in competitions similar to the tasks performed by rovers on the surfaces of Mars and the Moon. This year your university team has been selected to participate and you are the chief programmer of your team.

This year, the task of the competition is to collect valuable samples from the surface of Mars. Of course, it is a simulation area designed for the competition and the specifics are as follows:

  1. The planet Mars has been divided into certain Areas of Interest (AoI) where the valuable samples may be present. There are three possible samples: a rock sample, a water sample, and a micro-organism sample.
  2. The rover robot of your team must travel to these AoIs and collect all the samples as they are essential to determine whether life is sustainable in Mars.
  3. The distances between the AoIs and the location of the samples will be known beforehand. There maybe multiple roads between two AoIs but no road connects the same AoI with itself (What's the point, right?).
  4. The battery life of your rover robot is limited and the samples must be collected using minimum energy.
  5. The distance travelled by the robot is directly proportional to the battery life consumed.
  6. The robot will always start from a specific location and will have to carry all the samples to the retrieval AoI to end the competition.

Given the input parameters of the simulation area, find the minimum distance covered as output. Assume that it is always possible to carry all the samples to the retrieval location.

Input

There maybe T(1T10)T (1 \leq T \leq 10) simulations in the competition and you have to complete all of them.

Each simulation starts with six integers: N(1N100,000)N (1 \leq N \leq 100,000), the number of AoIs, M(0M100,000)M (0 \leq M \leq 100,000) - the number of roads connecting the AoIs, a,b,c(1a,b,cN)a, b, c (1 \leq a, b, c \leq N), the three sample locations and, r(1rN)r (1 \leq r \leq N), the retrieval location.

The next MM lines each contain three road parameters: u,v,w(1u,v,w100,000)u, v, w (1 \leq u, v, w \leq 100,000), where uu and vv are the connecting ends of the roads and, ww is the distance between the end AoIs. The starting location is always '1'.

Subtasks

  • Subtask 1 (40 points): The roads connecting the AoIs have identical distances.
  • Subtask 2 (60 points): The roads connecting the AoIs have variable distances.

Output

Output only one integer for every simulation: the distance travelled by the robot while collecting all the samples and returning to the retrieval location using minimum battery energy.

Samples

InputOutput
1
6 6 3 5 4 6
1 2 1
2 3 1
2 5 1
5 4 1
2 4 1
4 6 1
6
InputOutput
2
10 11 5 2 7 10
1 2 1
1 3 2
2 3 5
3 5 1
3 4 2
5 4 2
4 6 5
6 7 6
6 8 1
8 10 3
8 9 3
10 15 5 7 9 10
1 2 1
1 3 2
2 3 5
4 7 4
3 5 1
3 4 2
2 6 2
5 4 2
4 6 5
6 7 6
6 8 1
7 9 1
8 10 3
8 9 3
6 10 7
28
16

Dataset can be large, use fast I/O methods.

    Discussion

    Statistics


    94% Solution Ratio

    NirjhorEarliest, 1M ago

    prodip_bsmrstuFastest, 0.2s

    prodip_bsmrstuLightest, 10 MB

    NirjhorShortest, 1246B

    Submit

    Login to submit

    Toph uses cookies. By continuing you agree to our Cookie Policy.