采用dij+拓扑

#include<bits/stdc++.h>
using namespace std;
namespace FAST_IO
{
	template<typename T> void read(T &a)
	{
		a=0;
		int f=1;
		char c=getchar();
		while(!isdigit(c))
		{
			if(c=='-')
			{
				f=-1;
			}
			c=getchar();
		}
		while(isdigit(c))
		{
			a=a*10+c-'0';
			c=getchar();
		}
		a=a*f;
	}
	template <typename T> void write(T a)
	{
		if(a<0)
		{
			a=-a;
			putchar('-');
		}
		if(a>9)
		{
			write(a/10);
		}
		putchar(a%10+'0');
	}
	template <typename T> void writeln(T a)
	{
		write(a);
		puts("");
	}
}	
//#define int long long
queue<int> q;
const int maxn=3e4;
int t,r,p,s;
vector<pair<int,int> > g[maxn];
//vector<pair<int,int> > g2[maxn];
int visd[maxn];
int dis[maxn],belong[maxn],kzz;
int from1[maxn],to1[maxn],len1[maxn];
int in[maxn],vis[maxn];
vector<int> kuai[maxn];
void dfs(int now)
{
	visd[now]=true;
	belong[now]=kzz;
	kuai[kzz].push_back(now);
	for(int i=0;i<g[now].size();i++)
	{
		int to=g[now][i].first;
		if(visd[to])
		{
			continue;
		}
		dfs(to);
	}
}
void dij(int x)
{
	priority_queue<pair<int,int> > pq;
	for(int i=0;i<kuai[x].size();i++)
	{
		int to=kuai[x][i];
		pq.push(make_pair(-dis[to],to));
	}
	while(pq.size())
	{
		int from=pq.top().second;
		pq.pop();
		if(vis[from])
		{
			continue;
		}
		vis[from]=true;
		for(int i=0;i<g[from].size();i++)
		{
			int to=g[from][i].first,len=g[from][i].second;
			if(vis[to])
			{
				continue;
			}
			if(belong[to]!=belong[from])
			{
				in[belong[to]]--;
				if(!in[belong[to]])
				{
					q.push(belong[to]);
				}
			}
			if(dis[from]+len<dis[to])
			{
				dis[to]=dis[from]+len;
				if(belong[to]==belong[from])
				{
					pq.push(make_pair(-dis[to],to));
				}
			}
		}
	}
}
signed main()
{
	cin>>t>>r>>p>>s;
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	for(int i=1;i<=r;i++)
	{
		int from,to,len;
		cin>>from>>to>>len;
		g[from].push_back(make_pair(to,len));
		g[to].push_back(make_pair(from,len));
	}
	for(int i=1;i<=t;i++)
	{
		if(visd[i])
		{
			continue;
		}
		kzz++;
		dfs(i);
	}
	for(int i=1;i<=p;i++)
	{
		cin>>from1[i]>>to1[i]>>len1[i];
		//g2[belong[from1[i]]].push_back(make_pair(belong[to1[i]],len1[i]));
		g[from1[i]].push_back(make_pair(to1[i],len1[i]));
		in[belong[to1[i]]]++;
	}
	q.push(belong[s]);
	for(int i=1;i<=kzz;i++)
	{
		if(!in[i])
		{
			q.push(i);
		}
	}
	while(q.size())
	{
		int tmp=q.front();
		q.pop();
		dij(tmp);
	}
	for(int i=1;i<=t;i++)
	{
		if(dis[i]==0x3f3f3f3f)
		{
			cout<<"NO PATH"<<endl;
		}
		else
		{
			cout<<dis[i]<<endl;
		}
	}
}