bzoj#P2200. [Usaco2011 Jan]道路和航线

[Usaco2011 Jan]道路和航线

题目描述

Farmer John 正在一个新的销售区域对他的牛奶销售方案进行调查。

他想把牛奶送到 TT 个城镇,编号为 1,2,,T1,2,\ldots,T。这些城镇之间通过 RR 条道路和 PP 条航线连接。每条道路 ii 或者航线 ii 连接城镇 AiA_iBiB_i,花费为 CiC_i

对于道路,CiC_i 是非负数;然而航线的花费很神奇,花费 CiC_i 可能是负数。道路是双向的,可以从 AiA_iBiB_i,也可以从 BiB_iAiA_i,花费都是 CiC_i。然而航线与之不同,只可以从 AiA_iBiB_i

由于最近恐怖主义太嚣张,为了社会和谐,出台了一些政策保证:如果有一条航线可以从 AiA_iBiB_i,那么保证不可能通过一些道路和航线从 BiB_i 回到 AiA_i

由于 FJ 的奶牛世界公认十分给力,他需要运送奶牛到每一个城镇。他想找到从发送中心城镇 SS 把奶牛送到每个城镇的最便宜的方案,或者知道这是不可能的。

输入格式

第一行:四个空格隔开的整数:T,R,PT,R,P,和 SS

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

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

输出格式

11TT 行:从 SS 到达城镇 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

样例说明

一共六个城镇。在 (1,2)(1,2)(3,4)(3,4)(5,6)(5,6) 之间有道路,花费分别是 55551010。同时有三条航线:353\to5464\to6131\to3,花费分别是 100-100100-10010-10。FJ的中心城镇在城镇 44

FJ 的奶牛从 44 号城镇开始,可以通过道路到达 33 号城镇。然后他们会通过航线达到 5566 号城镇。但是不可能到达 1122 号城镇。

数据规模与约定

对于 100%100\% 的数据,$1\le T\le2.5\times 10^4,1\le S\le T,1\le R,P\le 5\times 10^4$,对于道路 0Ci1040\le C_i\le10^4,对于航线 104Ci104-10^4\le C_i\le10^4

来源

Gold