CCC '25 S4 - Floor is Lava - Olympiads Online Judge

CCC '25 S4 - Floor is Lava

Points: 12 (partial)

Time limit: 4.0s

Memory limit: 512M

Author:

Problem type

Canadian Computing Competition: 2025 Stage 1, Senior #4

You're trapped in a scorching dungeon with $N$ ~N~ rooms numbered from $1$ ~1~ to $N$ ~N~ connected by $M$ ~M~ tunnels. The $i$ ~i~-th tunnel connects rooms $a_i$ ~a_i~ and $b_i$ ~b_i~ in both directions, but the floor of the tunnel is covered in lava with temperature $c_i$ ~c_i~.

To help you navigate the lavatic tunnels, you are wearing a pair of heat-resistant boots that initially have a chilling level of $0$ ~0~. In order to step through lava with temperature $\ell$ ~\ell~, your boots must have the same chilling level $\ell$ ~\ell~; if the chilling level is too low then the lava will melt your boots, and if it's too high then your feet will freeze as you cross the tunnel.

Luckily, when you're standing in a room, you can increase or decrease the chilling level of your boots by $d$ ~d~ for a cost of $d$ ~d~ coins. You start in room $1$ ~1~ and would like to reach the exit which you know is located in room $N$ ~N~. What is the minimum cost to do so?

Input Specification

The first line of input contains two integers $N$ ~N~ and $M$ ~M~ $(1 \le N, M \le 200\,000)$ ~(1 \le N, M \le 200\,000)~.

The next $M$ ~M~ lines each contain three integers $a_i$ ~a_i~, $b_i$ ~b_i~, and $c_i$ ~c_i~ $(1 \le a_i, b_i \le N, a_i \neq b_i, 1 \le c_i \le 10^9)$ , describing the $i$ ~i~-th tunnel.

There is at most one tunnel connecting any pair of rooms, and it is possible to reach all other rooms from room $1$ ~1~.

The following table shows how the available $15$ ~15~ marks are distributed:

Marks	Additional constraints
2	$M = N-1$ ~M = N-1~
4	For all tunnels, $1 \le c_i \le 10$ ~1 \le c_i \le 10~
4	Each room has at most $5$ ~5~ outgoing tunnels
5	None

Output Specification

Output the minimum cost (in coins) to reach room $N$ ~N~ from room $1$ ~1~.

Sample Input

Sample Output

Explanation for Sample Output

$\text{[math]}$

A diagram of the dungeon is shown above. The optimal escape strategy is as follows:

Increase the chilling level to $3$ ~3~ for a cost of $3$ ~3~ coins.
Walk through the tunnel to room $2$ ~2~.
Decrease the chilling level to $2$ ~2~ for a cost of $1$ ~1~ coin.
Walk through the tunnel to room $3$ ~3~.
Increase the chilling level to $3$ ~3~ for a cost of $1$ ~1~ coin.
Walk through the tunnel to room $4$ ~4~.
Increase the chilling level to $7$ ~7~ for a cost of $4$ ~4~ coins.
Walk through the tunnel to room $5$ ~5~ and escape.

This has a total cost of $9$ ~9~ coins, and it can be shown that no cheaper route exists.

Comments

0

danplus6 commented on Feb. 15, 2026, 8:10 p.m.

do you pronounce "dijkstra's" as "jikstras" or "dikstras"

0

do_ur_homwork commented on Feb. 15, 2026, 8:20 p.m. ← edited →

I think the seccond one. bruce pronounces it that way so it must be.

Edit: This is what google says.

0

Crakxinator commented on Feb. 7, 2026, 9:36 p.m.

If u dont understand like me, search up Dijkstra's Algorithm.

0

Hyperreality commented on Feb. 6, 2026, 1:33 a.m.

Somehow, my algorithm is fast enough for Batch 3 but not Batch 1 (Case 10) 🤔

0

Hyperreality commented on Feb. 6, 2026, 2:04 a.m. ← edited →

Is this an issue with DMOJ itself? Case 9 and 10 for Batch 1 seem to take equivalent amounts of time when running the test data on my own machine, but Case 10 always gives TLE when submitting here (both with Python 3 or PyPy3). Edit: nvm, the test data seems to start at 02 for Case 1. I was comparing the wrong data

0

do_ur_homwork commented on Feb. 6, 2026, 3:15 a.m.

reason for batch 3 passing:

Each room has at most 5 outgoing tunnels