[USACO11JAN] Roads and Planes G

题目描述

有 $T$ 个城镇、$R$ 条双向道路和 $P$ 条单向航线。道路费用非负，航线费用可以为负。每条道路或航线从 $A_i$ 连接到 $B_i$，费用为 $C_i$。题目保证：对于任意航线 $A_i\to B_i$，无法通过道路和航线从 $B_i$ 返回 $A_i$。给定出发城镇 $S$，求从 $S$ 到每个城镇的最小费用。

输入格式

第一行输入 $T,R,P,S$。随后 $R$ 行每行输入 $A_i,B_i,C_i$，描述双向道路；再随后 $P$ 行按相同格式描述单向航线。

输出格式

输出 $T$ 行。第 $i$ 行为从 $S$ 到城镇 $i$ 的最小费用。若不可达，输出 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

说明与数据范围

$1\le T\le25000$，$1\le R,P\le50000$，$1\le S,A_i,B_i\le T$。道路费用满足 $0\le C_i\le10000$，航线费用满足 $-10000\le C_i\le10000$。样例中，城镇 $1,2$ 无法从 $4$ 到达。

来源

P3008