1503：道路和航线

题目描述

Farmer John 正在一个新的销售区域对他的牛奶销售方案进行调查。他想把牛奶送到 $T$ 个城镇，编号为 $1$ 到 $T$。这些城镇之间通过 $R$ 条道路（编号为 $1$ 到 $R$）和 $P$ 条航线（编号为 $1$ 到 $P$）连接。每条道路 $i$ 或者航线 $i$ 连接城镇 $A_i$ 到 $B_i$，花费为 $C_i$。

对于道路，$0 \le C_i \le 10^4$，然而航线的花费可能是负数。道路是双向的，可以从 $A_i$ 到 $B_i$，也可以从 $B_i$ 到 $A_i$，花费都是 $C_i$。然而航线与之不同，只可以从 $A_i$ 到 $B_i$。

事实上，由于最近恐怖主义太嚣张，为了社会和谐，出台了一些政策保证：如果有一条航线可以从 $A_i$ 到 $B_i$，那么保证不可能通过一些道路和航线从 $B_i$ 回到 $A_i$。由于 FJ 的奶牛世界公认十分给力，他需要运送奶牛到每一个城镇。他想找到从发送中心城镇 $S$ 把奶牛送到每个城镇的最便宜的方案，或者知道这是不可能的。

输入格式

第一行为四个空格隔开的整数：$T, R, P, S$；

第二到第 $R+1$ 行：三个空格隔开的整数（表示一条道路）：$A_i, B_i$ 和 $C_i$；

第 $R+2$ 到 $R+P+1$ 行：三个空格隔开的整数（表示一条航线）：$A_i, B_i$ 和 $C_i$。

输出格式

输出 $T$ 行，第 $i$ 行表示到达城镇 $i$ 的最小花费，如果不存在输出 NO PATH。

样例

样例输入 #1

6 3 3 4
1 2 5
3 4 5
5 6 10
3 5 -100
4 6 -100
1 3 -10

样例输出 #1

NO PATH
NO PATH
5
0
-95
-100

样例解释 #1

• $T=6$ 个城镇，$R=3$ 条道路，$P=3$ 条航线，起点 $S=4$。
• 道路（双向，费用非负）：
  1. $1 \leftrightarrow 2$，费用 $5$
  2. $3 \leftrightarrow 4$，费用 $5$
  3. $5 \leftrightarrow 6$，费用 $10$
• 航线（单向，费用可负）：
  1. $3 \rightarrow 5$，费用 $-100$
  2. $4 \rightarrow 6$，费用 $-100$
  3. $1 \rightarrow 3$，费用 $-10$

从起点 $4$ 出发：

• 到城镇 $1$：无法到达。因为从 $4$ 可以通过道路到 $3$，但从 $3$ 只能通过航线到 $5$，无法到 $1$。虽然有一条航线 $1 \rightarrow 3$，但方向是 $1$ 到 $3$，不能反向。所以输出 NO PATH。
• 到城镇 $2$：同样无法到达，理由类似。
• 到城镇 $3$：直接走道路 $4 \leftrightarrow 3$，费用 $5$。
• 到城镇 $4$：起点，费用 $0$。
• 到城镇 $5$：路径 $4 \rightarrow 3 \rightarrow 5$，费用为 $5 + (-100) = -95$。
• 到城镇 $6$：直接走航线 $4 \rightarrow 6$，费用 $-100$。

数据范围

• $1 \le T \le 2.5 \times 10^4$
• $1 \le R, P \le 5 \times 10^4$
• $1 \le A_i, B_i, S \le T$
• 对于所有道路，$0 \le C_i \le 10^4$
• 对于所有航线，$-10^4 \le C_i \le 10^4$

时空限制

• 时间限制：1000 ms
• 内存限制：65536 KB

注意：本题需要处理带有负权边（航线）但无负环（题目保证航线不会形成环，结合道路和航线整体无环）的最短路问题。由于图规模较大，需要采用高效的算法，如缩点（将道路连接的部分缩成连通块）后拓扑排序 + DAG 上 DP 或使用优化版的 SPFA（如 SLF、LLL 优化）或 Dijkstra 配合适当的处理。