wip

78. Interconnected Planets

Time Limit: 1 seconds

Memory Limit: 1024 MB

Rating: 1500

The Galactic Council has recently discovered a set of $N$ planets connected by $M$ bi-directional wormholes in the outer reaches of the universe. Each wormhole allows direct travel between two planets and has a certain cost associated with it due to energy consumption. Your mission is to travel from the starting planet $S$ to the destination planet $D$ while incurring the least possible travel cost. Given the information about the planets and wormholes, determine the minimum cost required to travel from planet $S$ to planet $D$. If it is impossible to reach the destination, return $-1$.

The first line contains three integers: $N$ $(1 ≤ N ≤ 10^5)$, $M$ $(0 ≤ M ≤ 2 \cdot 10^5)$, and $S (1 ≤ S ≤ N)$, representing the number of planets, the number of wormholes, and the starting planet, respectively. The second line contains the integer $D (1 ≤ D ≤ N)$, representing the destination planet. The next M lines contain three integers each: $u$, $v$, and $w$ $(1 ≤ u, v ≤ N, 1 ≤ w ≤ 10^9)$, representing a wormhole between planet $u$ and planet $v$ with a travel cost of $w$.

Output a single integer, the minimum cost to travel from planet $S$ to planet $D$. If there is no possible way to reach the destination, print $-1$.

Sample Input 0:
5 6 1
5
1 2 4
1 3 2
2 3 5
2 4 10
3 5 3
4 5 1

Sample Output 0:
5


Sample Input 1:
46 11 19
33
2 8 53
2 33 85
5 29 100
6 38 43
7 44 19
9 21 46
13 37 74
14 36 69
19 43 4
19 41 40
24 43 6

Sample Output 1:
-1

Not available for this problem.

KL Coding Cup October 2024 > Problem 16