Skip to content

14128: 【原4128】六月的雨

题目

题目描述

author: Lmxyy 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4128

Description

一场雨,把我困在这里。你冷漠的表情会让我伤心。

dhh经常出门不带伞。而上海的天气,emmm,你懂的。。。

经过了之前的跳高训练,dhh在xyy的训练下已经可以一飞冲天。dhh现在想要从宿舍出发,到体育馆去参加ACM班篮球比赛,为班争光。

有\(N\)个节点,编号为\(1 \sim N\)。有\(M\)条双向路连接了这些节点,其中第\(i\)条路连接了\(u_i\)和\(v_i\)这两个节点,且从一端走到另一端需要\(w_i\)秒。

宿舍在\(1\)号节点,体育馆在\(N\)号节点,保证dhh可以从宿舍走到体育馆。

在第\(0\)秒,dhh在宿舍。他的目标是尽早到达体育馆参加篮球赛。根据天气预报,接下来会下\(K\)次暴雨,第\(i\)次暴雨的时间为第\(l_i\)到\(r_i\)秒,且保证每次暴雨的时间互不重叠(包括起止时间)。由于dhh没有伞,所以下暴雨时他只能避雨。由于每个节点里都有一栋建筑物,而公路上没有任何可以避雨的地方,所以dhh在下雨时只能在某个节点的建筑物里面躲雨。

眼看dhh就要赶不上比赛了,xyy用魔法来帮助dhh赶上比赛。他的魔法能够将某条道路的两个端点合并为一个点(合并出的节点拥有原来两个节点的所有出边)。然后xyy的MP有限,但他最多只能用一次这个魔法。

所以,dhh想问你,他最少要多少秒才能到体育馆参加篮球赛?

Input Format

第一行三个非负整数,\(N,M,K,mode\),分别表示点数、边数、暴雨数以及xyy能否释放魔法帮助dhh。\(mode = 0\)表示xyy无法施放魔法,\(mode = 1\)表示xyy可以施放魔法。

接下来\(M\)行,每\(i\)行三个正整数\(u_i,v_i,w_i\)。

接下来\(K\)行,第\(i\)行两个整数\(l_i,r_i\)。

Output Format

输出一行一个整数,表示dhh最早多少秒可以到体育馆。

Sample Input 1

3 3 2 1
1 3 5
2 1 4
2 3 4
4 5
9 10

Sample Output 1

0

Sample Input 2

4 4 3 1
1 3 5
2 1 4
2 3 4
3 4 1000
4 5
9 10
11 10000

Sample Output 2

9

Data Range

| 数据点 | 数据特征 | | :-------------: | :----------------: | | \(1 \sim 2\) | \(mode = K = 0\) | | \(3 \sim 4\) | \(K = 0\) | | \(5 \sim 7\) | \(mode = 0\) | | \(8 \sim 10\) | 无明显特征 |

对于所有数据,\(2 \le N \le 10^5\),\(1 \le M \le 2 \times 10^5\),\(0 \le K \le 10^5\),\(1 \le w_i \le 10^4\),\(0 \le l_i < r_i \le 10^9\),且保证输入的暴雨时间互不相交,\(l_i\)严格递增。

Hint

对于一场\(l \sim r\)的暴雨,若dhh第\(r\)秒从节点出发,或第\(l\)秒到达某个节点,他都不会淋到雨。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!