4699. 树上的最短路
#4699. 树上的最短路
题目描述
下水道的主干路由n个节点和n-l条边组成，每条边有一个通过它所需的时间Ti。换言之，这是一棵n个节点的带权
树。现在，要用最快的速度赶往目标节点k。下水道有一些塌陷，这导致主干路的某一段路径可以通过该塌陷到另
一条路径。对于一个塌陷，我们用(L1，ri，L2，R2，c)来描述，即对于主干路上L1到R1路径上的任意节点x，L2到
r2路径上的任意节点y，都可以在c的时间内从x走到y。因为不知道自己所在的到底是哪个节点，所以要求出每个节
点到目标节点K的最短距离。注意边是单向的
输入格式
第一行两个数n，m，k，表示节点数、塌陷数和目标节点编号，空格分隔。
接下来n-l行，每行3个数x,y,t，表示主干路的一条边连接点x,y，通过的时间为t。
接下来m行，每行5个数L1，r1，L2，r2，c，表示一个塌陷。
N<=250000
m<=100000
1 < = L1,L2, R1, R2,x,y < = N
1< = t,c< = 2^31-1。
输出格式
n行，每行一个数，表示第i个节点到第k个节点的最短路径长度。
特别的，在第k行你应当输出0。
样例
样例输入
5 3 5
1 2 100
2 3 100
3 4 100
4 5 100
1 2 4 5 200
2 2 4 4 90
3 3 2 2 5
样例输出
200
190
195
100
0