题目内容

在2077年小塔所在的世界可以简化成一条数轴，小塔在位置$1$上，而小塔的目的地在$n$。

小塔的每分钟可以走一米，他每次可以选择往左走或往右走，在这条数轴上，还存在$m$个传送装置，每个装置连接着数轴上的两个点$(u,v)$，当小塔走到具有装置的点$u$时，其可以选择传送到点$v$，$v$点同理且每次传送耗时为$0$。

小塔现在希望你能帮他规划一下路线使得其到达目的地的时间是最少的。

思路

最短路问题，虽然只有1e3条边，但是点的下标太大了，考虑离散化最短路，记这m条边最小和最大的点的下标为mi和mx，则1到mi和mx到n都不能传送只能花费时间，将问题转化成从mi开始到mx的最短路问题，将每边的u，v都放进离散化数组，离散化后建边(除了传送，还要和相邻的点建边花费为坐标差)。最后跑一遍最短路即可

代码如下

cpp

#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[10005];
int u[10005],v[10005];