往返预算内的站点

难度：T2

【知识点：生成树与最短路辨析】

前置知识：本单元此前讲解的状态、边界与实现。

题目描述

对每个站点独立安排一次从 $s$ 出发并返回 $s$ 的往返，统计最短往返距离不超过 $L$ 的站点数。只去得了而回不来的站点不计入； $s$ 自身计入。

其中 $n$ 为顶点数，顶点编号为 $1$ 到 $n$ ； $m$ 为随后给出的带权边条数。每条带权边独占一行，依次为 $u,v,w$ ，表示从 $u$ 到 $v$ 的边及权值 $w$ ；无向边可双向通行，有向边只能从 $u$ 到 $v$ 通行。

输入 $n$ 、 $m$ 、 $s$ 、 $L$ 及 $m$ 条有向非负权边。每个站点独立从 $s$ 出发再返回 $s$ 。

输出往返最短距离不超过 $L$ 的站点数，包括 $s$ ；任一方向不可达不计。

$1\le n\le 100000$ ， $0\le m\le 200000$ ， $0\le w\le 10^9$ ， $0\le L\le 10^14$ 。

1 0 1 0