#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
题意整理;原题与输入输出格式对照。