求答案

詹沐恩

2025-11-02 17:00:02

发布于：广东

4阅读

0回复

0点赞

题目描述
最近小王所在的城市在修建地铁，已经有很多的地铁已经完工，但也有一些还在施工中。现在小王要出发去参加朋友的聚会，在出行时会尽可能的节省时间，地铁的速度非常快。乘地铁每公里只需
3
3 分钟，步行的话每公里需要
20
20 分钟。

小王从家里出发，通过导航发现，到达目的地有
n
n 条路，从导航来看到达每个目的地的时间都差不多，但是导航的数据并未实时更新，有些地方在修建地铁所以走不通，需要绕远路，绕路每公里需要
30
30 分钟。

如果时间足够的话，小王可以慢慢计算哪一条最快，可惜聚会就要开始了，小王不得不选取一条导航显示最快的一条。

如果
i
i 号点有地铁已完工，那么可以从
i
−
1
i−1 号点乘地铁到
i
i 号点；
如果
i
i 号点有地铁未完工，那么可以从
i
−
1
i−1 号点绕远路到
i
i 号点；
如果
i
i 号点没有地铁，那么可以从
i
−
1
i−1 号点步行到
i
i 号点；
输入格式
第一行输入
L
，
M
L，M。分别表示所选道路的长度和道路中地铁的数量；
接下来
M
M 行，为每个地铁的信息，每行
3
3 个数
x
，
l
，
r
x，l，r。分别表示地铁是否在完工（
0
0 未完工，
1
1 已完工），
l
，
r
l，r 表示地铁的范围；
输出格式
输出到达目的的时间；
样例
输入数据 1
50 3
1 1 20
0 21 30
1 40 50
输出数据 1
573
提示
样例 1 解析
小王处在
0
0 的位置，坐地铁到
20
20 ，路径
20
20 公里，共耗时
20
×
3

60
20×3=60；
小王处在
20
20 的位置，中间修地铁，绕路
10
10 公里到
30
30 的位置，共耗时
10
×
30
+
60

360
10×30+60=360；
小王处在
30
30 的位置，步行到
39
39 的位置，路径
9
9 公里，共耗时
9
×
20
+
360

540
9×20+360=540；
小王处在
39
39 的位置，坐地铁到
50
50 ，路径
11
11 公里，共耗时
11
×
3
+
540

573
11×3+540=573；
数据范围
20
%
20% 的数据满足，
L
≤
100
,
M
＜
100
L≤100,M＜100 ，地铁不会有重叠部分（边缘也不会）；
50
%
50% 的数据满足，
L
≤
10000
，
M
＜
10000
L≤10000，M＜10000 ，地铁不会有重叠部分（边缘也不会）；
70
%
70% 的数据满足，
L
≤
100000
,
M
＜
100000
L≤100000,M＜100000 ，地铁不会有重叠部分（边缘也不会）；
额外
10
%
10% 的数据满足，
L
≤
10000
，
M
＜
10000
L≤10000，M＜10000 ，地铁有重叠部分，只要存在有地铁部分就可以坐地铁；
额外
20
%
20% 的数据满足，
L
≤
100000
，
M
＜
100000
L≤100000，M＜100000 ，地铁有重叠部分，只要存在有地铁部分就可以坐地铁；
l
l 的下标可能为
0
0。