Finally had the motivation and time to finish writing this. Couple of weeks ago I took a class on the solutions of these problems. I struggled to provide a satisfactory intuition behind problem A, so here's an alternate explanation.
First, we need to be familiar with a modified version of Dijkstra's algorithms to calculate single source shortest path. This modification only helps us when the edge weights are small or when it's guaranteed that the length of any shortest path – if exists – is in the range $[0, W]$ for some small value $W$. It runs in linear time in $|V|$, $|E|$, and $W$, i.e. in $O(|V|+|E|+W)$, where $V$ is the vertex set and $E$ is the edge set of the graph. This modification was also included in the 3rd edition of Introduction to Algorithms as an exercise (exercise 24.3-8), so if you've read the chapter, you may have come across this modification.
Let's recall the standard implementation of Dijkstra's algorithm in C++:
for (int i = 1; i <= n; i++) distance[i] = INF; distance[x] = 0; q.push({0,x}); while (!q.empty()) { int a = q.top().second; q.pop(); if (processed[a]) continue; processed[a] = true; for (auto u : adj[a]) { int b = u.first, w = u.second; if (distance[a]+w < distance[b]) { distance[b] = distance[a]+w; q.push({distance[b],b}); } } }where q is a min priority queue.
Instead of using a priority queue, which takes $\log$ time to push and extract, we'll do something similar to Pigeonhole sort: create $W+1$ queues $q[0], q[1], \ldots, q[W]$, and when we detect a path from the source to $u$ that has $w$ length, we'll push that path (implementation-wise, just push the node $u$) in the $w$-th queue, that is, $q[w]$; in particular, we'll push the source node in $q[0]$ in the beginning of the algorithm. Throughout the algorithm, we'll process the queues in this order: $q[0], q[1], \ldots, q[W]$. Processing paths in the increasing order of their lengths and relaxing other nodes' shortest path via that path ensures the correctness of Dijkstra's algorithm. Note that, because weights are non-negative, new relaxed path will be added at the end of the upcoming queues.
The modified implementation will look something like this:
vector<queue<int>> q(W+1); for (int i = 1; i <= n; ++i) distance[i] = INF; distance[x] = 0; q[0].push(x); for(int len = 0; len <= W; ++len) { while(!q[len].empty()) { int u = q[len].front(); q[len].pop(); for(auto [v, w] : adj[u]) { if(distance[u] + w < distance[v]) { distance[v] = distance[u] + w; if(distance[v] <= W) { q[distance[v]].push(v); } } } } }
How does this trick help though? It's not like the statement will explicitly mention that "the shortest path length will be at most $W$". Hold on for a few more minutes. You're in for a treat!
Statement: We are given a weighted directed graph, consisting of $n$ vertices and $m$ edges. We should answer $q$ queries of two types:
For a directed weighted graph $G(V, E)$ and a list of $|V|$ real numbers $d_1, d_2, \ldots, d_{|V|}$, define another directed graph $G^\prime$ on $V$ which, for each directed edge $u \xrightarrow{w} v$ in $G$, has a directed edge $u \xrightarrow{w - (d_v - d_u)} v$. That is, both graphs are same exept for their edge weights.
If we take any path from $u$ to $v$ and measure its length in $G^\prime$, we'll see that most of the $d_u$ will cancel out, leaving only $-(d_v - d_u)$ plus the original edge weights from $G$. Furthermore, if we take any cycle, it's length in $G^\prime$ will be the same as in $G$. This has some neat implications:
Let's denote the graph before an update with $G$ and the graph after the update with $G^\prime$. Trivially, we could just run Dijkstra's algorithm using priority queue in $G^\prime$, but we can't because TL doesn't allow for an extra log factor. We can't use "linear" time trick either becuase the necessary conditions aren't guaranteed. To make things favourable, we'll apply the aforementioned trick of "superimposing a sequence $d$ over a graph" on $G^\prime$ (let's, for the sake of sanity, denote the graph after superimposing $d$ on $G^\prime$ with $G^\prime_d$), that is, for each edge $u \xrightarrow{w} v$ in $G^\prime$, the weight of the corresponding edge in $G^\prime_d$ will be $w - (d_v - d_u)$. We don't know what we should choose for $d$ yet, but what we do know is that $G^\prime_d$ should satisfy the following to actually use the "linear" time trick:
If we just wanted to fullfil (1), we could've just set $d_u = 0$ for all $u$, but that wouldn't help at all because the the shortest path could get as big as $10^{14}$. Recall that our source is 1 and the length of a shortest path from 1 to $u$ in $G^\prime_d$ is (sum of original edge weights) $- (d_u - d_1)$. To make this as small as possible, we should try to maximize $(d_u - d_1)$. Let's set $d_1 = 0$ because it doesn't really matter. Now we need to maximize $d_u$ under the following condition:
Rings a bell? This is a special case of linear programming and can be solved using shortest path algorithm (has been discussed in section 4 of chapter 24, i.e. 24.4, of Introduction to Algorithms). Ideally, we should set $d_u = \delta_{G^\prime}(1, u)$, where $\delta_G(u, v)$ is the length of a shortest path from $u$ to $v$ in the graph $G$, and all the shortest paths' length in $G^\prime_d$ should be 0. Welp, this is an awkward inception – weren't we trying to find $\delta_{G^\prime}$ in the first place?
Trust me, we can redeem this. Indeed, we may not know $\delta_{G^\prime}$, but we have a second best option at our disposal – we know $\delta_G(1, u)$ for all $u$; we already calculated this after the previous update. We can set $d_u = \delta_G(1, u)$, which also satisfies the inequality condition (verify it). After setting $d_u = \delta_{G}(1, u)$, shortest path in $G^\prime_d$ $\delta_{G^\prime_d}(1, u)$ will be $\delta_{G^\prime}(1, u) - \delta_{G}(1, u)$, and, lo and behold, what's the maximum value of $\delta_{G^\prime}(1, u) - \delta_{G}(1, u)$? Yes, you guessed it correct! $c$, and $c$ is small.
After finding the shortest paths in $G^\prime_d$ in $O(v + m + c)$ time, we can find $\delta_{G^\prime}(1, \cdot)$ using $\delta_{G}(1, \cdot)$.
That's all for today, and always remember to mark a processed node while running Dijkstra's algorithm :D
*sorry for the grammar and spelling mistakes