All Tracks Algorithms Graphs Shortest Path Algorithms Problem

Space smugglers

Algorithms, Dijkstra, Medium, Shortest-path


Nathan Reynolds is a famous smuggler and captain of a spaceship "Serenade". He was offered a potentially dangerous job on Ariel, one of the border planets of the star system. But to save all the "honest" earnings of the previous adventures, he decided to store them on one of the planets on the way to the border.

Star system is represented by $$n$$ planets and $$m$$ space tunnels between them. Space tunnel is one-way wormhole to travel from one planet to another, requiring an amount of gravitonium to perform the gravity jump. There may be several space tunnels between two planets, but no space tunnel leads to the same planet it starts from.

Your task as a first officer is to find the minimum amount of gravitonium to travel from the base planet to Ariel, visiting some other planet to store the earnings, and return back to base, picking up the earnings on the way back.

Note, that storing the earnings in a base planet or the planet, where the job is taking place, is not allowed. But it's allowed to visit Ariel with the earnings as long as you are not doing a job on this planet.

Input format

The first line of input contains four integers $$n$$, $$m$$, $$s$$ and $$t$$ — number of planets in a star system, number of space tunnels, the index number of the base planet and the index number of Ariel, respectively.

Each of the next $$m$$ lines contains three integers $$u$$, $$v$$ and $$g$$ — the planet, where the space tunnel starts, the planet, where the space tunnel goes to, and the amount of gravitonium required to travel through the space tunnel, respectively ().


$$ 2 \le n \le 10 ^ 5 $$
$$ 1 \le m \le 10 ^ 5 $$
$$ 1 \le s, t \le n $$, $$ s \ne t$$
$$ 1 \le u, v \le n $$
$$ 1 \le g \le 10 ^ 3$$

Output format

Output the minimum time required to travel from the base planet to Ariel, visiting some other planet to store the earnings, and return back to base, picking up the earnings on the way back, or output -1, if it's impossible.

5 9 1 2
1 3 1
1 5 5
2 5 1
3 1 10
3 4 5
4 2 1
5 1 5
5 3 100
5 4 5

One of possible ways to spend the minimum amount of gravitonium is to store the earnings on planet 5. Then, the path there and back is:

  1. $$1 \rightarrow 5$$, cost 5, store the earnings on this planet
  2. $$5 \rightarrow 4$$, cost 5
  3. $$4 \rightarrow 2$$, cost 1, do the job on Ariel
  4. $$2 \rightarrow 5$$, cost 1
  5. $$5 \rightarrow 1$$, cost 5, return to base

The total amount of requiring gravitonium is 17.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic


Initializing Code Editor...
Your Rating:


This Problem was Asked in


Challenge Name

February Easy '17

View All Notifications