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了，可以的话，请您参考添加页面，与大家一起分享你的题解！