Travelling Salesman Problem
题意翻译
C 国有 $n$ 个城市(编号为 $1$ 到 $n$),第 $i$ 个城市有美丽值 $a_i$ 和基价 $c_i$。
一位旅行商要旅行,他希望从城市 $1$ 开始,经过其他的每个城市正好一次,然后回到城市 $1$。
对于任意 $i\not=j$,从城市 $i$ 到达城市 $j$ 需要 $\max(c_i,a_j-a_i)$ 个金币。求旅行商完成旅行所需花费的最少金币数。
$2\leq n\leq10^5;0\leq a_i,c_i\leq10^9;$
题目描述
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.
输入输出格式
输入格式
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 a single integer — the minimum total cost.
输入输出样例
输入样例 #1
3
1 9
2 1
4 1
输出样例 #1
11
输入样例 #2
6
4 2
8 4
3 0
2 3
7 1
0 1
输出样例 #2
13
说明
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.