#540. 道路和航线

道路和航线

题目描述

原题来自:USACO 2011 Jan. Gold

Farmer John 正在一个新的销售区域对他的牛奶销售方案进行调查。他想把牛奶送到 TT 个城镇 ,编号为 11TT。这些城镇之间通过 RR 条道路(编号为 11RR)和 PP 条航线(编号为 11PP)连接。每条道路 ii 或者航线 ii 连接城镇 AiA_iBiB_i,花费为 CiC_i

对于道路,0Ci1040 \le C_i \le 10^4,然而航线的花费很神奇,花费 CiC_i 可能是负数。道路是双向的,可以从 AiA_iBiB_i,也可以从 BiB_iAiA_i,花费都是 CiC_i。然而航线与之不同,只可以从 AiA_iBiB_i

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

输入格式

第一行为四个空格隔开的整数:T,R,P,ST, R, P,S

第二到第 R+1R+1 行:三个空格隔开的整数(表示一条道路):Ai,BiA_i, B_iCiC_i

R+2R+2R+P+1R+P+1 行:三个空格隔开的整数(表示一条航线):Ai,BiA_i, B_iCiC_i

输出格式

输出 TT 行,第 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

一共六个城镇。在 112233445566 之间有道路,花费分别是 5,5,105,5,10。同时有三条航线:353\to 5464\to 6131\to 3,花费分别是 100,100,10-100,-100,-10。FJ 的中心城镇在城镇 44。FJ 的奶牛从 44 号城镇开始,可以通过道路到达 33 号城镇。然后他们会通过航线达到 5566 号城镇。但是不可能到达 1122 号城镇。

数据范围与提示

对于全部数据,$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$。保证对于所有道路,0Ci1040 \le C_i \le 10^4,对于所有航线,104Ci104-10^4 \le C_i \le 10^4