CPMagical CP Library

Problem solution · Python

CCC 2025 S4 - Floor is Lava

CCC 2025 S4 - Floor is Lava: a Python solution using heap or priority queue. Learn the idea, check the complexity, and read the full code, with credit to CCCSolutions.

Technique
Heap or priority queue
Source
CCCSolutions
Length
98 lines
Start with the idea.

Try the problem first. If you get stuck, read the approach below, then write your own solution. The full code is at the bottom.

Approach

Heap or priority queue

For CCC 2025 S4 - Floor is Lava, the implementation repeatedly takes the currently best candidate from a heap while inserting newly available choices.

  1. Define the priority key and whether the smallest or largest item should lead.
  2. Push each candidate when it becomes eligible.
  3. Discard stale entries when necessary and process the best live candidate.

Code notes

  • 98 lines of Python from the credited upstream file ccc25s4.py.
  • The implementation visibly relies on sequence storage, ordered lookup, work queue.
  • No explicit loop blocks detected.

Complexity

Count heap pushes and pops; each normally contributes a logarithmic factor in the heap size.

Check the problem constraints before deciding whether this complexity will pass.

Source

Code and credit

This code comes from CCCSolutions by CCCSolutions contributors · Milliken Mills High School and is used under the MIT licence.

Open problem ↗Original source ↗
Full codeCCC 2025 S4 - Floor is Lava · PythonPython
Use this to learn the idea, then write your own version.
# Advay Chandorkar, Glenforest SS (advayc)# py3 solution for 25' s4 import heapq # read number of levels (N) and number of tunnels (M)N, M = map(int, input().split()) # initialize a list of sets to store unique boot levels for each levellevels = [set() for _ in range(N)]tunnels = [] # read tunnel information and populate levels and tunnelsfor _ in range(M):    a, b, c = map(int, input().split())    a -= 1  # convert to 0-indexed    b -= 1    tunnels.append((a, b, c))    levels[a].add(c)    levels[b].add(c) # ensure level 0 has boot level 0levels[0].add(0) # sort boot levels for each levelfor i in range(N):    levels[i] = sorted(levels[i]) # calculate offset for node indexing in the graphoffset = [0] * (N + 1)total_nodes = 0for i in range(N):    offset[i] = total_nodes    total_nodes += len(levels[i])offset[N] = total_nodes # map each boot level to its index for quick accessmaps = []for i in range(N):    d = {}    for j, val in enumerate(levels[i]):        d[val] = j    maps.append(d) # initialize the graph with empty adjacency listsgraph = [[] for _ in range(total_nodes)] # add intra-room edges between adjacent boot levels with cost equal to their differencefor i in range(N):    base = offset[i]    L = levels[i]    for j in range(len(L) - 1):        u = base + j        v = base + j + 1        diff = L[j+1] - L[j]        graph[u].append((v, diff))        graph[v].append((u, diff)) # add tunnel edges with zero cost if the required boot level is availablefor a, b, c in tunnels:    u = offset[a] + maps[a][c]    v = offset[b] + maps[b][c]    graph[u].append((v, 0))    graph[v].append((u, 0)) INF = 10**18# initialize distances with infinitydist = [INF] * total_nodes # start from level 0 with boot level 0start_node = offset[0] + maps[0][0]dist[start_node] = 0 # use a min-heap for dijkstra's algorithmheap = []heapq.heappush(heap, (0, start_node)) # perform dijkstra's algorithm to find minimum distanceswhile heap:    d, u = heapq.heappop(heap)    if d != dist[u]:        continue    for v, cost in graph[u]:        nd = d + cost        if nd < dist[v]:            dist[v] = nd            heapq.heappush(heap, (nd, v)) # find the minimum distance to the last levelans = INFbase = offset[N-1]for j in range(len(levels[N-1])):    node = base + j    if dist[node] < ans:        ans = dist[node] print(ans)

Keep practising

Did this explanation save you time? I'm a Grade 11 student building this free library to make difficult algorithms easier to understand.

Buy me a coffee ↗