33OJ
登录 注册

#P17639. [ICPC 2019 Yinchuan R] Delivery Route

[ICPC 2019 Yinchuan R] Delivery Route

题目描述

小马是一家快递公司的老板。公司需要将包裹送达 nn 个办公室,办公室编号从 11 到 nn。特别地,第 ss 个办公室是这家快递公司的转运站。

这些办公室之间共有 xx 条普通的双向道路和 yy 条单向道路。如果快递车经过第 ii 条道路,将会消耗 cic_i 的能量。通常情况下,在一条道路上消耗的能量必须是非负的。然而,得益于实验性的充电轨道,某些单向道路上的消耗值可能为负。

除此之外,小马还获得了以下公开信息。有关部门承诺,如果存在一条从 aia_i 到 bib_i 的单向道路,则不可能从 bib_i 返回 aia_i。

为了避免快递车在路上抛锚,小刀想要找出从转运站到这些办公室的最低能量消耗。

输入格式

第一行包含四个整数 n (1≤n≤25000)n~(1 \le n \le 25000)、x,y (1≤x,y≤50000)x, y~(1 \le x, y \le 50000) 和 s (1≤s≤n)s~(1 \le s \le n)。接下来共有 x+yx+y 行,每行包含三个整数 ai,bi (1≤ai,bi≤n,ai≠bi)a_i, b_i~(1 \le a_i, b_i \le n, a_i \neq b_i) 和 ci (−10000≤ci≤10000)c_i~(-10000 \le c_i \le 10000),描述各条道路。所给的前 xx 条道路是普通的双向道路,后 yy 条道路是单向道路。

输出格式

输出应包含 nn 行,第 ii 行表示从第 ss 个办公室到达第 ii 个办公室的最小能量消耗(如果可能),若无法到达第 ii 个办公室,则输出 NO PATH。

6 3 3 4
1 2 5 
3 4 5
5 6 10
3 5 -100 
4 6 -100 
1 3 -10
NO PATH
NO PATH
5
0
-95 
-100

提示

翻译由 DeepSeek V4 Pro 完成