问题 Z: 道路与航线
内存限制：128 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：6
解决：4
题目描述
Farmer John is conducting research for a new milk contract in a new territory. He intends to distribute milk to T (1 <= T <= 25,000) towns conveniently numbered 1..T which are connected by up to R (1 <= R <= 50,000) roads conveniently numbered 1..R and/or P (1 <= P <= 50,000) airplane flights conveniently numbered 1..P.
Either road i or plane i connects town AiA_iAi (1 <= Ai <= T) to town BiB_iBi (1 <= Bi <= T) with traversal cost CiC_iCi. For roads, 0 <= Ci <= 10,000; however, due to the strange finances of the airlines, the cost for planes can be quite negative (-10,000 <= Ci <= 10,000).
Roads are bidirectional and can be traversed from Ai to BiB_iBi or BiB_iBi to AiA_iAi for the same cost; the cost of a road must be non-negative.
Planes, however, can only be used in the direction from Ai to BiB_iBi specified in the input. In fact, if there is a plane from Ai to Bi it is guaranteed that there is no way to return from Bi to Ai with any sequence of roads and planes due to recent antiterror regulation.
Farmer John is known around the world as the source of the world's finest dairy cows. He has in fact received orders for his cows from every single town. He therefore wants to find the cheapest price for delivery to each town from his distribution center in town S (1 <= S <= T) or to know that it is not possible if this is the case.
Either road i or plane i connects town AiA_iAi (1 <= Ai <= T) to town BiB_iBi (1 <= Bi <= T) with traversal cost CiC_iCi. For roads, 0 <= Ci <= 10,000; however, due to the strange finances of the airlines, the cost for planes can be quite negative (-10,000 <= Ci <= 10,000).
Roads are bidirectional and can be traversed from Ai to BiB_iBi or BiB_iBi to AiA_iAi for the same cost; the cost of a road must be non-negative.
Planes, however, can only be used in the direction from Ai to BiB_iBi specified in the input. In fact, if there is a plane from Ai to Bi it is guaranteed that there is no way to return from Bi to Ai with any sequence of roads and planes due to recent antiterror regulation.
Farmer John is known around the world as the source of the world's finest dairy cows. He has in fact received orders for his cows from every single town. He therefore wants to find the cheapest price for delivery to each town from his distribution center in town S (1 <= S <= T) or to know that it is not possible if this is the case.
输入
* Line 1: Four space separated integers: T, R, P, and S
* Lines 2..R+1: Three space separated integers describing a road: Ai, Bi and Ci
* Lines R+2..R+P+1: Three space separated integers describing a plane: Ai, Bi and Ci
* Lines 2..R+1: Three space separated integers describing a road: Ai, Bi and Ci
* Lines R+2..R+P+1: Three space separated integers describing a plane: Ai, Bi and Ci
输出
* Lines 1..T: The minimum cost to get from town S to town i, or 'NO PATH' if this is not possible
样例输入 复制
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提示
6 towns. There are roads between town 1 and town 2, town 3 and town 4, and town 5 and town 6 with costs 5, 5 and 10; there are planes from town 3 to town 5, from town 4 to town 6, and from town 1 to town 3 with costs -100, - 100 and -10. FJ is based in town 4.
FJ's cows begin at town 4, and can get to town 3 on the road. They can get to towns 5 and 6 using planes from towns 3 and 4. However, there is no way to get to towns 1 and 2, since they cannot go
backwards on the plane from 1 to 3.
FJ's cows begin at town 4, and can get to town 3 on the road. They can get to towns 5 and 6 using planes from towns 3 and 4. However, there is no way to get to towns 1 and 2, since they cannot go
backwards on the plane from 1 to 3.