TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P5737
  • 题目
  • P5737树上的最短路
    限制 : 时间限制 : 50000 MS   空间限制 : - KB
    评测说明 : 5s,512m
    问题描述

    下水道的主干路由n个节点和n-1条边组成,每条边有一个通过它所需的时间Ti。换言之,这是一棵n个节点的带权 树。
    现在,要用最快的速度赶往目标节点k。下水道有一些塌陷,这导致主干路的某一段路径可以通过该塌陷到另 一条路径。对于一个塌陷,我们用(L1,R1,L2,R2,c)来描述,即对于主干路上L1到R1路径上的任意节点x,L2到 R2路径上的任意节点y,都可以在c的时间内从x走到y。
    因为不知道自己所在的到底是哪个节点,所以要求出每个节 点到目标节点K的最短距离。注意边是单向的

    输入格式

    第一行两个数n,m,k,表示节点数、塌陷数和目标节点编号,空格分隔。
    接下来n-1行,每行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


    来源  bzoj4699