最短路问题,虽然只有1e3条边,但是点的下标太大了,考虑离散化最短路,记这m条边最小和最大的点的下标为mi和mx,则1到mi和mx到n都不能传送只能花费时间,将问题转化成从mi开始到mx的最短路问题,将每边的u,v都放进离散化数组,离散化后建边(除了传送,还要和相邻的点建边花费为坐标差)。最后跑一遍最短路即可
#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[10005];
int u[10005],v[10005];
在2077年小红所在的世界可以简化成一条数轴,小红在位置1上,而小红的目的地在n。
小红的每分钟可以走一米,他每次可以选择往左走或往右走,在这条数轴上,还存在m个传送装置,每个装置连接着数轴上的两个点(u,v),当小红走到具有装置的点u时,其可以选择传送到点v,v点同理且每次传送耗时为0。
小红现在希望你能帮他规划一下路线使得其到达目的地的时间是最少的。
第一行为n,m,表示目的地坐标和装置个数。
接下来有m行,每行为两个整数表示装置连接的两个点u,v。
1≤n≤109,1≤m≤104,1≤u,v≤n。
输出为一行,表示小红最少需要的时间。
输入
10 2
1 5
4 10
输出
1
说明
小红首先在1依靠装置传送到位置5,然后小红再向左走一米花费一分钟,达到4,再利用传送装置到达10,所以小红所需的时间为1分钟。
输入
10 3
2 3
3 4
4 5
输出
6
说明
小红先走到2,花费一分钟,然后连续传送到5。
小红从5走到10需要五分钟。
所有小红一共需要六分钟。