Description：

一个图，有 $m_1$ 条无向边， $m_2$ 条有向边，无向边边权为正，有向边无保证，但保证经过有向边不能回去，问从 $s$ 到所有点的最短路。

$1\leqslant n\leqslant10^5 $

Solution：

首先这题不能直接用 $dijkstra$ ，而且还卡 $SPFA$ ，但是注意到把所有无向边缩点后是一个 $DAG$ ，那么我们就可以在强连通分量中跑 $dijkstra$ ，然后在强连通分量之间用拓扑排序更新，具体的做法是先将所有强连通分量缩点，然后在拓扑排序的时候每次取出来一个强连通分量，把所有中的点都压到堆里，然后跑多源 $dijkstra$ ，但是在 $dijkstra$ 的时候只把同一个强连通分量中的点压到堆里，别的点只更新距离不放到堆里，然后最后在减一下度数，把这时度数为 $0$ 的强连通分量放到队列中，这样就可以保证每个强连通分量都是在所有他前面的强连通分量更新完了时候更新。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<queue>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

int n,m1,m2,st;

#define MAXN 50010

struct edge

{

	int to,nxt,v;

}e[MAXN * 3];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,int c)

{

	e[++edgenum] = (edge){b,lin[a],c};lin[a] = edgenum;

	return;

}

int dfn[MAXN],low[MAXN],tot = 0;

bool v[MAXN];

stack<int> s;

int ins[MAXN],scc = 0;

vector<int> p[MAXN];

void tarjan(int k)

{

	dfn[k] = low[k] = ++tot;

	s.push(k);v[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(dfn[e[i].to] == 0)

		{

			tarjan(e[i].to);

			low[k] = min(low[k],low[e[i].to]);

		}

		else if(v[e[i].to])

		{

			low[k] = min(low[k],dfn[e[i].to]);

		}

	}

	if(low[k] == dfn[k])

	{

		int t;

		++scc;

		do

		{

			t = s.top();s.pop();

			ins[t] = scc;v[t] = false;

			p[scc].push_back(t);

		}while(t != k);

	}

	return;

}

int ind[MAXN];

int d[MAXN];

#define INF 0x3f3f3f3f

int main()

{

	scanf("%d%d%d%d",&n,&m1,&m2,&st);

	int a,b,c;

	for(int i = 1;i <= m1;++i)

	{

		scanf("%d%d%d",&a,&b,&c);

		add(a,b,c);add(b,a,c);

	}

	for(int i = 1;i <= m2;++i)

	{

		scanf("%d%d%d",&a,&b,&c);

		add(a,b,c);

	}

	for(int i = 1;i <= n;++i)

		if(dfn[i] == 0)tarjan(i);

	for(int k = 1;k <= n;++k)

		for(int i = lin[k];i != 0;i = e[i].nxt)

			if(ins[k] != ins[e[i].to])++ind[ins[e[i].to]];

	queue<int> q;

	for(int i = 1;i <= scc;++i)

		if(ind[i] == 0)q.push(i);

	memset(d,0x3f,sizeof(d));

	d[st] = 0;

	while(!q.empty())

	{

		int k = q.front();q.pop();

		priority_queue< pair<int,int> > pq;

		for(vector<int>::iterator it = p[k].begin();it != p[k].end();++it)

			if(d[*it] != INF)pq.push(make_pair(-d[*it],*it));

		while(!pq.empty())

		{

			int k = pq.top().second;pq.pop();

			if(v[k])continue;

			v[k] = true;

			for(int i = lin[k];i != 0;i = e[i].nxt)

			{

				if(d[e[i].to] > d[k] + e[i].v)

				{

					d[e[i].to] = d[k] + e[i].v;

					if(ins[k] == ins[e[i].to])

						pq.push(make_pair(-d[e[i].to],e[i].to));

				}

			}

		}

		for(vector<int>::iterator it = p[k].begin();it != p[k].end();++it)

			for(int i = lin[*it];i != 0;i = e[i].nxt)

				if(ins[*it] != ins[e[i].to] && (--ind[ins[e[i].to]]) == 0)

					q.push(ins[e[i].to]);

	}

	for(int i = 1;i <= n;++i)

	{

		if(d[i] != INF)printf("%d\n",d[i]);

		else puts("NO PATH");

	}

	return 0;

}