#251. 道路与航线

道路与航线

题目描述

有 T 个城镇,R 条双向道路和 P 条单向航线。道路费用非负,航线费用可为负。若有航线从 a 到 b,保证不能从 b 通过道路或航线返回 a。求起点 S 到每个城镇的最短费用。

输入格式

首行 T、R、P、S;随后 R 行道路 a、b、c,再随后 P 行航线 a、b、c。城镇编号从1开始。

输出格式

按城镇编号输出 T 行最短费用;不可达时输出 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

题意整理;原题与输入输出格式对照。