In the absence of the editorial, I'll provide a brief explanation of my solution for those who may be struggling (This could be seen as a self-note rather than a complete explanation) : Use any shortest-path algorithm to find the shortest distance from Source and Sink to other nodes. Construct a graph so-called shortest-path graph G in which an edge u->v presents if and only if d[u] + w(u,v) == d[v] where d[x] is the shortest distance from Source to x and w(u,v) is the weight of that edge. Consider the induced graph G' of vertices that can reach Sink from G, if the deleted edge is not a bridge of G', then the shortest distance from Source to Sink won't change. Otherwise, that bridge separates G into two disjoint components, the new shortest distance is d_source[u] + w(u,v) + d_sink[v] assuming that u belongs to the source's and v belongs to the sinkscomponent. By applying sweepline algorithm + a min heap / multiset, we can precompute the answer for all such bridges in O(N + ElogN) times.