题目描述
原题来自：USACO 2011 Jan. Gold
Farmer John 正在一个新的销售区域对他的牛奶销售方案进行调查。他想把牛奶送到
T
T 个城镇 ，编号为
1
1 到
T
T。这些城镇之间通过
R
R 条道路（编号为
1
1 到
R
R）和
P
P 条航线（编号为
1
1 到
P
P）连接。每条道路
i
i 或者航线
i
i 连接城镇
A_i
A
i
到
B_i
Bi，花费为
C_i
Ci。
对于道路，
0 \le C_i \le 10^4
0≤Ci≤104，然而航线的花费很神奇，花费
C_i
Ci 可能是负数。道路是双向的，可以从
A_i
Ai 到
B_i
Bi，也可以从
B_i
B
i
到
A_i
Ai，花费都是
C_i
Ci。然而航线与之不同，只可以从
A_i
A
i
到
B_i
Bi。
事实上，由于最近恐怖主义太嚣张，为了社会和谐，出台了一些政策保证：如果有一条航线可以从
A_i
Ai 到
B_i
Bi，那么保证不可能通过一些道路和航线从
B_i
Bi 回到
A_i
Ai。由于 FJ 的奶牛世界公认十分给力，他需要运送奶牛到每一个城镇。他想找到从发送中心城镇
S
S 把奶牛送到每个城镇的最便宜的方案，或者知道这是不可能的。
输入
第一行为四个空格隔开的整数：
T, R, P,S
T,R,P,S；
第二到第
R+1
R+1 行：三个空格隔开的整数（表示一条道路）：
A_i, B_i
Ai
,B
i
和
C_i
Ci
；
第
R+2
R+2 到
R+P+1
R+P+1 行：三个空格隔开的整数（表示一条航线）：
A_i, B_i
Ai
,Bi
和
C_i
Ci
。
输出
输出
T
T 行，第
i
i 行表示到达城镇
i
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
1 和
2
2，
3
3 和
4
4，
5
5 和
6
6 之间有道路，花费分别是
5,5,10
5,5,10。同时有三条航线：
3\to 5
3→5，
4\to 6
4→6 和
1\to 3
1→3，花费分别是
-100,-100,-10
−100,−100,−10。FJ 的中心城镇在城镇
4
4。FJ 的奶牛从
4
4 号城镇开始，可以通过道路到达
3
3 号城镇。然后他们会通过航线达到
5
5 和
6
6 号城镇。但是不可能到达
1
1 和
2
2 号城镇。
数据范围与提示
对于全部数据，
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
1≤T≤2.5×104,1≤R,P≤5×104,1≤Ai
,Bi
,S≤T。保证对于所有道路，
0 \le C_i \le 10^4
0≤Ci
≤104，对于所有航线，
-10^4 \le C_i \le 10^4
−104≤Ci
≤104。
来源/分类
ybttg 最短路 拓扑排序