该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

P3008 [USACO11JAN] Roads and Planes G

题目描述

题面描述

给定 一个含 $n$ 个点 的混合图（含 $m$ 条无向边 和 $p$ 条有向边）， 无向边的长度非负，有向边的长度可能为负，保证不会有包含有向边的环。

求点 $st$ 到每个点的最小距离。

输入格式

共 $m+p+1$ 行。

第 $1$ 行四个整数 $n \ m \ p \ st \ \ ( 1 \le n \le 25,000 , 1 \le m \le 50,000 , 1 \le p \le 50,000)$ 。

下来 $m$ 行，每行三个整数 $A_i \ B_i \ C_i \ (0 \le C_i \le 10,000)$ ，描述一条连接点 $A_i$ 和 点 $B_i$ 无向边，边的长度为 $C_i$。

下来 $p$ 行，每行三个整数 $A_i \ B_i \ C_i \ ( -10,000 \le C_i \le 10,000)$ ，描述一条从点 $A_i$ 出发到点 $B_i$ 的有向边，边的长度为 $C_i$。

输出格式

共 $n$ 行，第 $i$ 行输出点 $st$ 到点 $i$ 的最小距离。

如果不能到达，输出NO PATH

输入输出样例 #1

输入 #1

6 3 3 4 
1 2 5 
3 4 5 
5 6 10 
3 5 -100 
4 6 -100 
1 3 -10

输出 #1

NO PATH 
NO PATH 
5 
0 
-95 
-100