This problem can be solved with a trick of representing intervals as edges. A typical application of this trick is the following problem:

There is a graph with \(N\) edges and \(0\) edges. Perform for \(i=1,2,\ldots,M\) in order:

• Given integers \(l_i,r_i,L_i,R_i,w_i\), add edges from vertices \(a\ (l_i\leq a\leq r_i)\) to vertices \(b\ (L_i\leq b\leq R_i)\), each of weight \(w_i\).

Find the shortest distance from vertex \(s\) to each vertex on the constructed graph.

If you try to solve it naively, there will be \(O(N^2M)\) edges. The trick of representing intervals as edges aims to reduce the edges by constructing the graph in a “good” way.

In order to reduce edges, we define additional vertices, so that each vertex represent an interval in a segment tree. The following figure will help understand the concept well.

(For international readers: here we are adding edges of cost \(C\) each from \([1,4]\) to \([3,7]\).)

(Credit: https://x.com/noshi91/status/1193177214453338113 )

This graph has \(O(N+M)\) vertices and \(O(N + M \log N)\) edges, so the shortest distance can be found with Dijkstra’s algorithm in \(O(N\log N+M\log^2 N)\) time.

　

Problems can be solved with similar trick (spoiler alert)

• (NIKKEI Programming Contest 2019-2) Shortest Path on a Line

• (CF406 div.1 B) Legacy

• (JOI ²⁰²²⁄₂₀₂₃ Spring Seminar C) Passport

  • Translated problem statement: there are countries \(1,\ldots,N\). If you have a passport issued at country \(i\), you are allowed to visit countries \(L_i,\ldots,R_i\) (\(L_i\leq i\leq R_i\)). In a travel, you can do the following any number of times in any order: move to a country that a passport you have allows, or acquire a passport issued at the country you are staying. Answer \(Q\) independent questions: if you start your travel with only one passport from country \(X_i\), how many more passport do you need to acquire until you reach the state where your passports cover all \(N\) countries (or print \(-1\) if it is impossible)?

---

The same trick of reducing edges can be applied to the original problem too.

Consider how to construct the graph. Assuming vertex \(1\) is in the west and vertex \(N\) in the east, first consider trains in the east direction. For each node in a segment tree, for the getting-on side, manage “the minimum cost required to reach the eastmost station within the corresponding interval,” and for getting-off side, “the minimum cost required to reach the westmost station within the corresponding interval.”

The graph will look like this:

• Getting-on side:

• Getting-off side:

Then trains with \((l,r,L,R)=(1,2,4,6)\) can be represented as follows:

Specifically,

• Define a sur-vertex \(A\) for getting on, and \(B\) for getting off.
• For each node within the interval for getting on, add an edge from that vertex to vertex \(A\). If that node represents \([a,b]\), set the edge weight to \(x_r-x_b\).
• Add an edge from vertex \(A\) to vertex \(B\) with edge weight \(x_L-x_r+c\).
• For each node within the interval for getting off, add an edge from vertex \(B\) to that vertex. If that node represents \([a,b]\), set the edge weight to \(x_a-x_L\).

One can assert using the figure above that after this procedure, there is a path from any vertex \(u\ (1\leq u\leq 2)\) to vertex \(v\ (4\leq v\leq 6)\) with weight \(x_v-x_u+c\).

Trains in the west direction can be represented in the same way.

By connecting the graphs representing west-bound trains and east-bound train, the distance from vertex \(0\) can be computed with Dijkstra’s algorithm. The graph has \(O(N+M)\) vertices and \(O(N + M \log N)\) edges, so the computational complexity is \(O(N\log N+M\log^2 N) \).

By applying trivial contractions, the number of vertices can be reduced to \(5N'+M\) (where \(N'\) is the smallest power of two greater than or equal to \(N\)).