题面中充满了对大家的期望 ^_^
展览会（exhibition）
from xjr，题解 by xjr
算法一
妈妈我会写循环！
第一重枚举第一个传送门放哪，第二重枚举第二个传送门放哪，然后再套个循环计算所有人需要花多少时间就好啦。
时间复杂度：$O(n^3)$
期望得分：30分。
算法二
我们发现实际上每个计划的方向并不重要，因为对于计划 $(a,b)$ 我们可以想象成两个点从 $a$ 和 $b$ 分别出发，走到最近的传送门（这一点如果你写了上面的暴力就可以理解了）。
所以我们可以把所有 $a$ 和 $b$ 揉到一起排序，然后靠左的部分一定要走到左边的传送门，靠右的部分一定要走到右边的传送门。
我们枚举左右部分的分界线。令左边的所有坐标分别为 $A_1,A_2,\cdots,A_p$，右边的所有坐标分别是 $B_1,B_2,\cdots,B_q$，令左边的传送门坐标为 $L$，右边传送门坐标为 $R$，那么我们需要最小化 $\sum_{i=1}^p {|Ai−L|} + \sum_{i=1}^q {|Bi−R|}$，不难发现前半部分 $L$ 和后半部分 $R$ 取一个中位数，然后暴力算答案就好了。
$a=b$ 的部分就是启发你想中位数的
时间复杂度：$O(n \log n+n^2)$
期望得分：60分
算法三
我们发现预处理一下前缀和，可以在枚举分界线之后 $O(1)$ 计算答案！
时间复杂度：$O(n \log n)$
期望得分：100分
带环最短路（cyclepath）
from xjr，题解 by xjr
算法一
妈妈我会写爆搜！
从 $1$ 号节点出发 dfs，记录一下路径，如果有一个点被重复经过了，说明走了一个环，最后到达 $n$ 并且已经走了一个环就更新答案。
时间复杂度：$O(不一定跑得过)$
期望得分：0~20分（我并没有写爆搜所以不知道有多少分）
算法二
诶我的爆搜为啥得了 30 分？
因为 $n=m$ 时只有唯一的路径（或不存在解）。
时间复杂度：同算法一
期望得分：30分
算法三
每个点都有一个长度为 $1$ 的自环！这是全世界最小的环了。
算出 $1$ 到 $n$ 的最短路，然后加 $1$ 就好了。
时间复杂度：$O((n+m) \log n)$
期望得分：结合算法一或二，40分
算法四
我们可以找一条边 $a \rightarrow b$，然后 $b$ 到 $a$ 的最短路加这条边的边权就是一个环的大小了。再把环的大小加上 $1$ 到 $a$ 的距离和 $a$ 到 $n$ 的距离就是一个合法方案的答案了。
于是 floyed 处理出每两个点间的最短路。
时间复杂度：$O(n^3)$
期望得分：结合算法三，70分
算法五
一条带环路径一定要经过某个点至少两次，所以我们可以关注一下一条路径上经过的某个点。
设 $f(i,j)$ 表示从 $1$ 到 $i$ 的路径中经过了 $j$ 一次的最短路（如果已经经过某个点两次，则 $j=0$）。然后分情况转移，跑最短路就好啦。细节留给你们思考。
时间复杂度：$O((n^2+nm) \log n)$
期望得分：100分
摆直线（setline）
from xjr，题解 by xjr
非常抱歉这题大样例出锅了。。。$k$ 和 $Y_i$ 变成了 $10^9$ 范围。。。
不过就当给大家做一个 long long 检测吧。。。
算法一
对于每个询问，直线需要经过第 $a$ 个点（以下简称点 $a$），而且直线斜率已经固定了，那么直线的解析式就可以算出来了。
然后通过解析式算出横坐标在 $[l,r]$ 之间的点的目标位置，和它本身的纵坐标的差取个绝对值然后求和就好了。
时间复杂度：$O(nq)$
期望得分：20分
算法二
如果所有总坐标都相同，那么就是一排高度相同的点移到直线上，相当于两个等差数列求和。
时间复杂度：$O(n+q)$
期望得分：结合算法一，30分
算法三
如果每组询问都有 $a=1$，那么就是直线一直固定，每个点移动到这个直线的代价也是固定的。
那么处理一下前缀和，每次询问也能 $O(1)$ 回答了。
时间复杂度：$O(n+q)$
期望得分：结合算法一&二，40分
算法四
$k=0$，即直线水平，每个点到直线的距离就是总坐标的差的绝对值，绝对值要分正负讨论。
我们可以将询问离线，按询问中的点 $a$ 纵坐标升序排序，同时将所有点按纵坐标排序。那么随着点 $a$ 的总坐标的增加，每个点的纵坐标和点 $a$ 纵坐标的大小关系只会变化一次，也就是正负性只会变化一次。所以我们可以维护两个树状数组分别维护点的纵坐标的前缀和与点的纵坐标相反数的前缀和，当某点正负性变化后，把它从一个树状数组中删除再加到另一个树状数组中就好了。
时间复杂度：$O((n+q) \log n)$
期望得分：80分
算法五
$k \ne 0$，也一样，只不过把询问按照过点 $a$ 的直线的纵截距排序，同时每个点按照过这个点的斜率为 $k$ 的直线的纵截距排序就好了。
时间复杂度：$O((n+q) \log n)$
期望得分：100分
最后，感谢验题人 wzj52501
