稀疏图到达阈值

难度：T2

【知识点：堆优化Dijkstra】

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

题目描述

给出有向带权图、源点 $s$ 和距离上限 $L$。每个目的地都单独从 $s$ 出发，统计最短距离不超过 $L$ 的顶点数，包括源点自身，但不计不可达的点。

输入格式

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

输入$n$、$m$、$s$、$L$与$m$条有向非负边。每个目的地单独从$s$出发。

输出格式

输出最短距离不超过$L$的站点数，包括源点，不包含不可达点。

数据范围

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

样例输入

1 0 1 0

样例输出

1

样例输入 2

4 3 1 3
1 2 2
2 3 2
1 3 5

样例输出 2

2

样例说明 2

源点距离为零，点 $2$ 距离为 $2$；点 $3$ 距离为 $4$ 超限，点 $4$ 不可达。