博客

题目描述

给定一个由 n 个点和 n-1 条边构成的连通图（即为一棵树）。每条边都有一个权值，

表示该边的长度。

除了原本存在 n-1 条边，在这棵树上，还存在着 m 条捷径。每条捷径可以用五元组

( u1,v1 ,u2 ,v2 ,L )表示：在树上路径( u2,v2 )上的每个点到树上路径( u1,v1 ) 上

的每个点，都存在一条长度为 L 的边。注意此处的捷径是单向的，而不是双向的。

对于树上的某一个点 S ，你需要求出它到其它各点的最短路。

输入数据

第一行三个正整数 n, m, S。

接下来 n-1 行，每行三个正整数 u, v, L，描述一条边。

接下来 m 行，每行一个五元组( u1,v1 ,u2 ,v2 ,L) ，描述一条捷径。

输出数据

输出 n 行，为点 S 到各个点的最小花费。

样例输入

5 3 5

1 2 100

2 3 100

3 4 100

4 5 100

1 2 4 5 200

2 2 4 4 200

3 3 2 2 5

样例输出

200

200

200

100

0

数据范围

对于 20%的数据，满足 n,m≤1000。

对于另 20%的数据，保证树的形态为一条链。

对于 100%的数据，满足 1≤n≤250000，1≤m≤100000。

题中所有边的长度均为正整数（int 类型）。

如果是一条链的话，当然是线段树优化建边了。

树上的话只需要剖分然后再用线段树就可以了。