Description
Farmer John正在一个新的销售区域对他的牛奶销售方案进行调查。他想把牛奶送到T个城镇 (1 <= T <= 25,000)，编号为1T。这些城镇之间通过R条道路 (1 <= R <= 50,000，编号为1到R) 和P条航线 (1 <= P <= 50,000，编号为1到P) 连接。每条道路i或者航线i连接城镇A_i (1 <= A_i <= T)到B_i (1 <= B_i <= T)，花费为C_i。对于道路，0 <= C_i <= 10,000;然而航线的花费很神奇，花费C_i可能是负数(-10,000 <= C_i <= 10,000)。道路是双向的，可以从A_i到B_i，也可以从B_i到A_i，花费都是C_i。然而航线与之不同，只可以从A_i到B_i。事实上，由于最近恐怖主义太嚣张，为了社会和谐，出台 了一些政策保证：如果有一条航线可以从A_i到B_i，那么保证不可能通过一些道路和航线从B_i回到A_i。由于FJ的奶牛世界公认十分给力，他需要运送奶牛到每一个城镇。他想找到从发送中心城镇S(1 <= S <= T) 把奶牛送到每个城镇的最便宜的方案，或者知道这是不可能的。
Input
- 第1行：四个空格隔开的整数: T, R, P, and S
- 第2到R+1行：三个空格隔开的整数（表示一条道路）：A_i, B_i 和 C_i
- 第R+2到R+P+1行：三个空格隔开的整数（表示一条航线）：A_i, B_i 和 C_i
Output
- 第1到T行：从S到达城镇i的最小花费，如果不存在输出"NO PATH"。
Sample Input
6 3 3 4
1 2 5
3 4 5
5 6 10
3 5 -100
4 6 -100
1 3 -10
样例输入解释：
一共六个城镇。在1-2，3-4，5-6之间有道路，花费分别是5，5，10。同时有三条航线：3->5，4->6和1->3，花费分别是-100，-100，-10。FJ的中心城镇在城镇4。
Sample Output
NO PATH
NO PATH
5
0
-95
-100
样例输出解释：
FJ的奶牛从4号城镇开始，可以通过道路到达3号城镇。然后他们会通过航线达到5和6号城镇。但是不可能到达1和2号城镇。
这题裸的单源最短路对吧，负边权直接上SPFA就好了。。。
然后你就可以获得TLE的好成绩，当然，不排除-Owys的优化
于是SPFA就有了一个优化，SLF优化，可以水过去，但是我没写
我们还是来讨论一下正解如何写。为什么这题不能用dijkstra，因为它有负边权。但是我们仔细观察发现，负边权只能是航线，而且航线只会连接两个无法直接到到的联通块，也就是说，我们可以在联通块内跑dijkstra
那么块与块之间的联系呢？这题缩完点后就是个DAG，那么我们就可以拓扑了，用拓扑处理块与块之间的关系，块内直接dijkstra，那么这题就做完了
然后有一些细节问题：
- 拓扑序需要从S所在联通块开始，因此入度要做一些更改
- 一个联通块开始dijkstra的时候，需要把所有的因为航线确定的点都扔到初始堆里面
/*program from Wolfycz*/
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 1e9
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
inline int read(){
int x=0,f=1;char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
return x*f;
}
inline void print(int x){
if (x>=10) print(x/10);
putchar(x%10+'0');
}
const int N=2.5e4,M=5e4;
struct S1{
int pre[(M<<1)+10],now[N+10],child[(M<<1)+10],val[(M<<1)+10],tot;
void join(int x,int y,int z){pre[++tot]=now[x],now[x]=tot,child[tot]=y,val[tot]=z;}
void insert(int x,int y,int z){join(x,y,z),join(y,x,z);}
}Rod;
struct S2{
int pre[M+10],now[N+10],child[M+10],val[M+10],tot;
void join(int x,int y,int z){pre[++tot]=now[x],now[x]=tot,child[tot]=y,val[tot]=z;}
}Pla;
struct S3{
#define ls (p<<1)
#define rs (p<<1|1)
#define fa (p>>1)
struct node{
int x,v;
bool operator <(const node &a)const{return v<a.v;}
}Q[N+10];
int tot;
void insert(int x,int v){
Q[++tot]=(node){x,v};
int p=tot;
while (p!=1&&Q[p]<Q[fa]) swap(Q[p],Q[fa]),p=fa;
}
void Delete(){
Q[1]=Q[tot--];
int p=1,son;
while (ls<=tot){
if (rs>tot||Q[ls]<Q[rs]) son=ls;
else son=rs;
if (Q[son]<Q[p]) swap(Q[son],Q[p]),p=son;
else break;
}
}
}Heap;
int from[M+10],to[M+10];//航线边的起始和结束
int col[N+10],deg[N+10],dis[N+10];//点所属联通块编号；联通块度数；每个点的距离
int h[N+10];
bool vis[N+10];
vector<pair<int,int> >vec[N+10];
int n,m,q,S,size;
void dfs(int x){//大水漫灌法
if (col[x]==size) return;
col[x]=size;
for (int p=Rod.now[x],son=Rod.child[p];p;p=Rod.pre[p],son=Rod.child[p]) dfs(son);
}
void Get_deg(int x){//从S所在联通块开始，从新确定度数
if (vis[x]) return;
vis[x]=1;
for (int p=Pla.now[x],son=Pla.child[p];p;p=Pla.pre[p],son=Pla.child[p]) deg[son]++,Get_deg(son);
}
void Dijkstra(int type){
for (int i=0;i<(int)vec[type].size();i++) Heap.insert(vec[type][i].first,vec[type][i].second);
while (Heap.tot){
int Now=Heap.Q[1].x;
Heap.Delete();
if (vis[Now]) continue;
vis[Now]=1;
for (int p=Rod.now[Now],son=Rod.child[p];p;p=Rod.pre[p],son=Rod.child[p]){
if (dis[son]>dis[Now]+Rod.val[p]){
dis[son]=dis[Now]+Rod.val[p];
Heap.insert(son,dis[son]);
}
}
}
}
void topo(){
memset(vis,0,sizeof(vis));
int head=1,tail=1;
h[1]=col[S],vec[col[S]].push_back(make_pair(S,dis[S]=0));
for (;head<=tail;head++){
int Now=h[head];
Dijkstra(Now);
for (int p=Pla.now[Now],son=Pla.child[p];p;p=Pla.pre[p],son=Pla.child[p]){
vec[son].push_back(make_pair(to[p],dis[to[p]]=min(dis[to[p]],dis[from[p]]+Pla.val[p])));//记得取min
if (!(--deg[son])) h[++tail]=son;
}
}
}
int main(){
n=read(),m=read(),q=read(),S=read();
memset(dis,63,sizeof(dis));
for (int i=1;i<=m;i++){
int x=read(),y=read(),z=read();
Rod.insert(x,y,z);
}
for (int i=1;i<=n;i++) if (!col[i]) ++size,dfs(i);
for (int i=1;i<=q;i++){
int x=read(),y=read(),z=read();
Pla.join(col[x],col[y],z),from[Pla.tot]=x,to[Pla.tot]=y;
}
Get_deg(col[S]);
topo();
for (int i=1;i<=n;i++) printf(dis[i]>inf?"NO PATH
":"%d
",dis[i]);
return 0;
}