Here is the solution:
function flightDiscount(n, edges):
adj = array of n + 1 empty lists
for (u, v, price) in edges:
adj[u].append((v, price))
dist = 2D array of size (n + 1) x 2, all infinity
dist[1][0] = 0
pq = min-heap with (0, 1, 0)
while pq is not empty:
(cost, u, used) = pq.pop()
if cost > dist[u][used]:
continue
for (v, price) in adj[u]:
if cost + price < dist[v][used]:
dist[v][used] = cost + price
pq.push((dist[v][used], v, used))
if used == 0 and cost + price / 2 < dist[v][1]:
dist[v][1] = cost + price / 2
pq.push((dist[v][1], v, 1))
return min(dist[n][0], dist[n][1])
This runs in time and uses space.