#P2141. 第3题-传送门2077
-
1000ms
Tried: 54
Accepted: 8
Difficulty: 7
所属公司 :
京东
时间 :2024年9月28日
第3题-传送门2077
思路
最短路问题,虽然只有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≤109,1≤m≤104,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需要五分钟。
所有小红一共需要六分钟。