#PU995. USACO 2020 January Contest, Gold — Problem 3. Springboards

    ID: 1533 传统题 文件IO:boards 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:jan20来源:usaco.orgscoring:equal_test_cases最短路

USACO 2020 January Contest, Gold — Problem 3. Springboards

USACO 2020 January Contest, Gold — Problem 3. Springboards

题目描述

Bessie is in a 2D grid where walking is permitted only in directions parallel to one of the coordinate axes. She starts at the point (0,0)(0,0) and wishes to reach (N,N)(N,N) (1≤N≤1091\le N\le 10^9). To help her out, there are PP (1≤P≤1051\le P\le 10^5) springboards on the grid. Each springboard is at a fixed point (x1,y1)(x_1,y_1) and if Bessie uses it, she will land at a point (x2,y2)(x_2,y_2). Bessie is a progress-oriented cow, so she only permits herself to walk up or right, never left nor down. Likewise, each springboard is configured to never go left nor down. What is the minimum distance Bessie needs to walk?

输入格式

The fist line contains two space-separated integers NN and PP. The next PP lines each contains four integers, x1x_1, y1y_1, x2x_2, y2y_2, where x1≤x2x_1 \le x_2 and y1≤y2.y_1 \le y_2. All springboard and target locations are distinct.

输出格式

(见题面原文)

数据范围

Test cases 2-5 satisfy P≤1000P \le 1000. Test cases 6-15 satisfy no additional constraints.

样例

样例 1

3 2
0 1 0 2
1 2 2 3
3
Bessie's best path is:
Bessie walks from (0,0) to (0,1) (1 unit).
Bessie springs to (0,2).
Bessie walks from (0,2) to (1,2) (1 unit).
Bessie springs to (2,3).
Bessie walks from (2,3) to (3,3) (1 unit).
The total walking length of Bessie's path is 3 units.
Problem credits: Pedro Paredes