Travelling Salesman Problem
Contest: Codeforces Round 712 (Div. 1)
Difficulty rating: 2200
Tags: binary search, data structures, dp, greedy, shortest paths, sortings, two pointers

There are $$$n$$$ cities numbered from $$$1$$$ to $$$n$$$, and city $$$i$$$ has beauty $$$a_i$$$.

A salesman wants to start at city $$$1$$$, visit every city exactly once, and return to city $$$1$$$.

For all $$$i\ne j$$$, a flight from city $$$i$$$ to city $$$j$$$ costs $$$\max(c_i,a_j-a_i)$$$ dollars, where $$$c_i$$$ is the price floor enforced by city $$$i$$$. Note that there is no absolute value. Find the minimum total cost for the salesman to complete his trip.

Input format:
The first line contains a single integer $$$n$$$ ($$$2\le n\le 10^5$$$) — the number of cities.

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$a_i$$$, $$$c_i$$$ ($$$0\le a_i,c_i\le 10^9$$$) — the beauty and price floor of the $$$i$$$-th city.

Output format:
Output a single integer — the minimum total cost.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, we can travel in order $$$1\to 3\to 2\to 1$$$.

- The flight $$$1\to 3$$$ costs $$$\max(c_1,a_3-a_1)=\max(9,4-1)=9$$$.
- The flight $$$3\to 2$$$ costs $$$\max(c_3, a_2-a_3)=\max(1,2-4)=1$$$.
- The flight $$$2\to 1$$$ costs $$$\max(c_2,a_1-a_2)=\max(1,1-2)=1$$$.

The total cost is $$$11$$$, and we cannot do better.

Example input:
3
1 9
2 1
4 1

Example output:
11

Example input:
6
4 2
8 4
3 0
2 3
7 1
0 1

Example output:
13

Editorial:
Let's reindex the cities so they are in increasing order of beauty. Note that it doesn't matter which city we call the start: the trip will be a cycle visiting every city exactly once.
Let's rewrite the cost of a flight $$$i\to j$$$ as $$$$$$\max(c_i, a_j-a_i)=c_i+\max(0, a_j-a_i-c_i).$$$$$$
Since we always need to leave each city exactly once, we can ignore the $$$c_i$$$ term from all flights and only try to minimize the sum of $$$\max(0,a_j-a_i-c_i).$$$
Note that a flight to a city of smaller beauty is always free in the adjusted cost. So all we need is a path from $$$a_1$$$ to $$$a_n$$$, and the rest of the trip can be done for free. Also, any valid trip will contain a path from $$$a_1$$$ to $$$a_n$$$, so the shortest path is optimal.
Solution 1
All we have to do is encode the graph without storing all edges explicitly, and we can simply run Dijkstra's algorithm to find the shortest path. Add the following edges:
1. $$$a_i\to a_{i-1}$$$ with weight $$$0$$$.
2. $$$i\to j$$$ with weight $$$0$$$, where $$$j$$$ is the largest index with $$$a_j-a_i-c_i\le 0$$$. The index $$$j$$$ can be found with binary search.
3. $$$i\to j+1$$$ with weight $$$\max(0, a_{j+1}-a_i-c_i)$$$ where $$$j$$$ is the same as before.
Every edge in this new graph corresponds to an edge in the original graph, and every edge in the original graph corresponds to a path in the new graph with at most the same cost. So the distance from $$$a_1$$$ to $$$a_n$$$ is preserved.
Solution 2
A simpler solution is to compute for all $$$i>1$$$, the minimum possible cost of the first trip reaching $$$a_i$$$ or larger. It's easy to see that any path must have at least this cost, and we can construct a path of this cost since moving to smaller $$$a_i$$$ is free. It corresponds to the following summation.
$$$$$$\sum_{i=2}^n \max(0, a_i-\max_{j<i}(a_j+c_j))$$$$$$
Complexity is $$$O(n\log n)$$$.