A5967. 「ICPC PacNW 2017 Div.1」David 的旅程
编程题
省选/NOI-
知识点
题目描述
**译自 ICPC PacificNW 2017 H [Avoiding Airports](http://codeforces.com/gym/101615/attachments/download/6308/20172018-acmicpc-pacific-northwest-regional-contest-div-1-en.pdf)**
David 要完成一个旅行计划，这个计划要在 $n$ 个城市中选择一个乘坐飞机的方案。他在时刻 0 从第 $1$ 个城市出发，最后到达 $n$ 号城市。
城市分别编号为 $1\dots n$。城市之间由 $m$ 条航班线路相连。
David 已经查看了这些航班的时刻表，第 $i$ 个航班将从城市 $u_i$ 飞往城市 $v_i$，在时刻 $s_i$ 起飞，时刻 $e_i$ 到达。
David 是一个很讨厌等待的人，他在等待过长时间后会有挫败感。如果他**在机场**等待了 $t$ 的时间，他将感到 $t^2$ 的挫败感。
请帮助 David 规划一个挫败感之和最小的路线，不一定花的时间最短，只需要最让他舒服就行了（他真的很讨厌等待！）。
保证不存在两个航班起飞时间相同，保证不存在两个航班到达时间相同。
David 要完成一个旅行计划，这个计划要在 $n$ 个城市中选择一个乘坐飞机的方案。他在时刻 0 从第 $1$ 个城市出发，最后到达 $n$ 号城市。
城市分别编号为 $1\dots n$。城市之间由 $m$ 条航班线路相连。
David 已经查看了这些航班的时刻表，第 $i$ 个航班将从城市 $u_i$ 飞往城市 $v_i$，在时刻 $s_i$ 起飞，时刻 $e_i$ 到达。
David 是一个很讨厌等待的人，他在等待过长时间后会有挫败感。如果他**在机场**等待了 $t$ 的时间，他将感到 $t^2$ 的挫败感。
请帮助 David 规划一个挫败感之和最小的路线，不一定花的时间最短，只需要最让他舒服就行了（他真的很讨厌等待！）。
保证不存在两个航班起飞时间相同，保证不存在两个航班到达时间相同。
输入格式
第一行两个整数 $n$，$m$ 分别表示城市的数目，航班的数目。
接下来 $m$ 行是航班的信息，第 $i + 1$ 行四个整数，$u_i,$ $v_i,$ $s_i,$ $e_i$。
接下来 $m$ 行是航班的信息，第 $i + 1$ 行四个整数，$u_i,$ $v_i,$ $s_i,$ $e_i$。
输出格式
一行一个数，答案。
输入输出样例
输入 #1
5 8 1 2 1 10 2 4 11 16 2 1 9 12 3 5 28 100 1 2 3 8 4 3 20 21 1 3 13 27 3 5 23 24
输出 #1
12
输入 #2
3 5 1 1 10 20 1 2 30 40 1 2 50 60 1 2 70 80 2 3 90 95
输出 #2
1900
说明/提示
$2 \leq n \leq 2\times 10^5,$ $1 \leq m \leq 2\times 10^5,$ $1 \leq u_i,v_i \leq n,$ $0 \leq s_i , e_i \leq 10^6$。
数据保证不存在两个航班起飞时间相同，保证不存在两个航班到达时间相同。
数据保证不存在两个航班起飞时间相同，保证不存在两个航班到达时间相同。