2025 S4 - Floor is Lava

1# Advay Chandorkar, Glenforest SS (advayc)
2# py3 solution for 25' s4
3
4import heapq
5
6# read number of levels (N) and number of tunnels (M)
7N, M = map(int, input().split())
8
9# initialize a list of sets to store unique boot levels for each level
10levels = [set() for _ in range(N)]
11tunnels = []
12
13# read tunnel information and populate levels and tunnels
14for _ in range(M):
15    a, b, c = map(int, input().split())
16    a -= 1  # convert to 0-indexed
17    b -= 1
18    tunnels.append((a, b, c))
19    levels[a].add(c)
20    levels[b].add(c)
21
22# ensure level 0 has boot level 0
23levels[0].add(0)
24
25# sort boot levels for each level
26for i in range(N):
27    levels[i] = sorted(levels[i])
28
29# calculate offset for node indexing in the graph
30offset = [0] * (N + 1)
31total_nodes = 0
32for i in range(N):
33    offset[i] = total_nodes
34    total_nodes += len(levels[i])
35offset[N] = total_nodes
36
37# map each boot level to its index for quick access
38maps = []
39for i in range(N):
40    d = {}
41    for j, val in enumerate(levels[i]):
42        d[val] = j
43    maps.append(d)
44
45# initialize the graph with empty adjacency lists
46graph = [[] for _ in range(total_nodes)]
47
48# add intra-room edges between adjacent boot levels with cost equal to their difference
49for i in range(N):
50    base = offset[i]
51    L = levels[i]
52    for j in range(len(L) - 1):
53        u = base + j
54        v = base + j + 1
55        diff = L[j+1] - L[j]
56        graph[u].append((v, diff))
57        graph[v].append((u, diff))
58
59# add tunnel edges with zero cost if the required boot level is available
60for a, b, c in tunnels:
61    u = offset[a] + maps[a][c]
62    v = offset[b] + maps[b][c]
63    graph[u].append((v, 0))
64    graph[v].append((u, 0))
65
66INF = 10**18
67# initialize distances with infinity
68dist = [INF] * total_nodes
69
70# start from level 0 with boot level 0
71start_node = offset[0] + maps[0][0]
72dist[start_node] = 0
73
74# use a min-heap for dijkstra's algorithm
75heap = []
76heapq.heappush(heap, (0, start_node))
77
78# perform dijkstra's algorithm to find minimum distances
79while heap:
80    d, u = heapq.heappop(heap)
81    if d != dist[u]:
82        continue
83    for v, cost in graph[u]:
84        nd = d + cost
85        if nd < dist[v]:
86            dist[v] = nd
87            heapq.heappush(heap, (nd, v))
88
89# find the minimum distance to the last level
90ans = INF
91base = offset[N-1]
92for j in range(len(levels[N-1])):
93    node = base + j
94    if dist[node] < ans:
95        ans = dist[node]
96
97print(ans)
98

1// Daniel Zhang, Pinetree Secondary
2// Dijkstra on edges instead, simpler implementation, harder to find
3
4#include <bits/stdc++.h>
5
6using namespace std;
7
8using ll = long long;
9using State = tuple<ll, ll, ll>;
10
11int vis[200001], edges[200001];
12vector<pair<ll, ll>> graph[200001];
13
14int main() {
15    int n, m; cin >> n >> m;
16    for (int i = 0; i < m; i++) {
17        int u, v, w; cin >> u >> v >> w;
18        graph[u].push_back({v, i});
19        graph[v].push_back({u, i});
20        edges[i] = w;
21    }
22    
23    priority_queue<State, vector<State>, greater<>> pq;
24    vector<ll> best(m + 1, LLONG_MAX);
25    
26    pq.push({0, 1, m});
27    
28    while (!pq.empty()) {
29        auto [c, a, i] = pq.top(); pq.pop();
30        
31        if (vis[i]) continue;
32        vis[i] = 1;
33        
34        if (a == n) {
35            cout << c;
36            return 0;
37        }
38        
39        for (auto [b, j] : graph[a]) {
40            if (vis[j]) continue;
41            ll new_c = c + abs(edges[i] - edges[j]);
42            if (new_c < best[j]) {
43                best[j] = new_c;
44                pq.push({new_c, b, j});
45            }
46        }
47    }
48}