思路

最短路问题，虽然只有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];
vector<int>alls;
vector<pair<int,int>>g[30005];
int get(int x){
	return lower_bound(alls.begin(), alls.end(), x) - alls.begin();
}
int dis[30005];
int vis[30005];
int inf=INT_MAX;
struct node{
	int w,u;
	bool operator < (const node &a)const{
		return a.w<w;
	}
};
void dijkstra(int s){
	int siz=alls.size();
	priority_queue<node>q;
	for(int i=1;i<siz;i++) dis[i]=inf;
	for(int i=1;i<siz;i++) vis[i]=0;
	dis[s]=0;
	q.push({0,s});
	while(q.size()){
		auto [w,u]=q.top();
		q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(auto [v,w1]:g[u]){
			if(dis[v]>w+w1){
				dis[v]=w+w1;
				if(!vis[v])q.push({dis[v],v});
			}
		}
	}
}
int main() {
	cin>>n>>m;
	alls.push_back(0);
	int ans=0,mi=1e9,mx=0;
	for(int i=1;i<=m;i++){
		cin>>u[i]>>v[i];
		alls.push_back(u[i]);
		alls.push_back(v[i]);
		mi=min({mi,u[i],v[i]});
		mx=max({mx,u[i],v[i]});
	}
	ans+=mi-1;
	ans+=n-mx;
	//转化为mi到mx的最小距离
	sort(alls.begin(), alls.end());
	alls.erase(unique(alls.begin(), alls.end()), alls.end());
	for(int i=1;i<=m;i++){
		int a=get(u[i]),b=get(v[i]);
		g[a].push_back({b,0});
		g[b].push_back({a,0});
	}
	int sz=alls.size();
	for(int i=1;i<sz;i++){
		if(i>1) g[i].push_back({i-1,alls[i]-alls[i-1]});
		if(i<sz-1) g[i].push_back({i+1,alls[i+1]-alls[i]});
	}
	dijkstra(1);
	cout<<ans+dis[sz-1]<<'\n';
	return 0;
}

python

import heapq

n, m = map(int, input().split())
u = [0] * 10005
v = [0] * 10005
alls = [0]
g = [[] for _ in range(30005)]
dis = [float('inf')] * 30005
vis = [0] * 30005

inf = float('inf')

def get(x):
    return alls.index(x)

def dijkstra(s):
    siz = len(alls)
    dis[s] = 0
    q = [(0, s)]
    while q:
        w, u = heapq.heappop(q)
        if vis[u]:
            continue
        vis[u] = 1
        for v, w1 in g[u]:
            if dis[v] > w + w1:
                dis[v] = w + w1
                if not vis[v]:
                    heapq.heappush(q, (dis[v], v))

ans = 0
mi, mx = int(1e9), 0

for i in range(1, m + 1):
    u[i], v[i] = map(int, input().split())
    alls.append(u[i])
    alls.append(v[i])
    mi = min(mi, u[i], v[i])
    mx = max(mx, u[i], v[i])

ans += mi - 1
ans += n - mx

# 去重并排序
alls = sorted(set(alls))

for i in range(1, m + 1):
    a = get(u[i])
    b = get(v[i])
    g[a].append((b, 0))
    g[b].append((a, 0))

sz = len(alls)
for i in range(1, sz):
    if i > 1:
        g[i].append((i - 1, alls[i] - alls[i - 1]))
    if i < sz - 1:
        g[i].append((i + 1, alls[i + 1] - alls[i]))

dijkstra(1)

print(ans + dis[sz - 1])

java

import java.util.*;

public class Main {
    static int n, m;
    static int[] u = new int[10005], v = new int[10005];
    static List<Integer> alls = new ArrayList<>();
    static List<List<Pair>> g = new ArrayList<>();
    static int[] dis = new int[30005];
    static int[] vis = new int[30005];
    static int inf = Integer.MAX_VALUE;

    static class Pair {
        int v, w;
        Pair(int v, int w) {
            this.v = v;
            this.w = w;
        }
    }

    static class Node implements Comparable<Node> {
        int w, u;
        Node(int w, int u) {
            this.w = w;
            this.u = u;
        }

        public int compareTo(Node a) {
            return Integer.compare(this.w, a.w); // 比较时按距离从小到大排序
        }
    }

    static int get(int x) {
        return alls.indexOf(x);  // 获取数值在去重后数组中的索引
    }

    static void dijkstra(int s) {
        int siz = alls.size();
        PriorityQueue<Node> q = new PriorityQueue<>();
        Arrays.fill(dis, 1, siz, inf);  // 初始化距离为无穷大
        Arrays.fill(vis, 1, siz, 0);  // 初始化访问标志为0
        dis[s] = 0;
        q.add(new Node(0, s));

        while (!q.isEmpty()) {
            Node top = q.poll();
            int w = top.w, u = top.u;
            if (vis[u] == 1) continue;
            vis[u] = 1;

            for (Pair p : g.get(u)) {
                int v = p.v, w1 = p.w;
                if (dis[v] > w + w1) {
                    dis[v] = w + w1;
                    if (vis[v] == 0) q.add(new Node(dis[v], v));
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        alls.add(0);  // 添加虚拟点0
        int ans = 0, mi = (int) 1e9, mx = 0;

        for (int i = 0; i <= 30000; i++) {
            g.add(new ArrayList<>());  // 初始化图结构
        }

        for (int i = 1; i <= m; i++) {
            u[i] = sc.nextInt();
            v[i] = sc.nextInt();
            alls.add(u[i]);
            alls.add(v[i]);
            mi = Math.min(mi, Math.min(u[i], v[i]));
            mx = Math.max(mx, Math.max(u[i], v[i]));
        }

        ans += mi - 1;  // 计算左边界到1的步数
        ans += n - mx;  // 计算右边界到n的步数

        // 去重并排序
        Collections.sort(alls);
        alls = new ArrayList<>(new HashSet<>(alls));
        Collections.sort(alls);  // 需要再次排序

        // 构建图结构
        for (int i = 1; i <= m; i++) {
            int a = get(u[i]), b = get(v[i]);
            g.get(a).add(new Pair(b, 0));
            g.get(b).add(new Pair(a, 0));
        }

        int sz = alls.size();
        for (int i = 1; i < sz; i++) {
            if (i > 1) g.get(i).add(new Pair(i - 1, alls.get(i) - alls.get(i - 1)));
            if (i < sz - 1) g.get(i).add(new Pair(i + 1, alls.get(i + 1) - alls.get(i)));
        }

        dijkstra(1);  // 从1号点开始做Dijkstra

        System.out.println(ans + dis[sz - 1]);  // 输出结果
    }
}

题目内容

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

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

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

输入描述

第一行为$n,m$，表示目的地坐标和装置个数。

接下来有$m$行，每行为两个整数表示装置连接的两个点$u,v$。

$1≤ n ≤ 10^9 ,1≤ m ≤10^4 ,1≤u,v≤n$。

输出描述

输出为一行，表示小红最少需要的时间。

样例1

输入

10 2
1 5
4 10

输出

1

说明

小红首先在$1$依靠装置传送到位置$5$，然后小红再向左走一米花费一分钟，达到$4$，再利用传送装置到达$10$，所以小红所需的时间为$1$分钟。

样例2

输入

10 3
2 3
3 4
4 5

输出

6

说明

小红先走到$2$，花费一分钟，然后连续传送到$5$。

小红从$5$走到$10$需要五分钟。

所有小红一共需要六分钟。