题目链接：Delivery Route

就是有负权的最短路，但是卡了spfa，由于x条路是双向的且为正，故我们可以缩点之后对块内跑Dijkstra，然后拓扑排序合并答案。

但是我们对spfa优化一下就可以了（卡常专家）。

我们都知道spfa有一个优化是SLF，就是用双端队列。

这道题我们再加上一个容错值，如果当前的队首值大于当前要插入的值加上容错值，那么当前值放到队首，否则队尾。

然后再来一个优化，就是随机数大法，随便判断下点的大小选择是否交换（超级重要，随机数防卡），则队列首位交换。

就OK啦！！！

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int inf=0x3f3f3f3f;
const int N=25010;
int n,x,y,s,d[N],eps;	bool vis[N];
vector<int> v1[N],v2[N];
inline void add(int a,int b,int c){v1[a].push_back(b); v2[a].push_back(c);}
inline void spfa(){
	deque<int> q; q.push_back(s); vis[s]=1; memset(d,inf,sizeof d); d[s]=0;
	while(q.size()){
		if(q.front()>q.back())	swap(q.front(),q.back()); 
		int u=q.front(); q.pop_front();	vis[u]=0;
		for(int i=0,v,w;i<v1[u].size();i++){
			v=v1[u][i],w=v2[u][i];
			if(d[v]>d[u]+w){
				d[v]=d[u]+w;	if(vis[v])	continue;
				if(q.size()&&q.front()+eps<w)	q.push_front(v);
				else	q.push_back(v);	vis[v]=1;
			}
		}
	}
}
signed main(){
	scanf("%d %d %d %d",&n,&x,&y,&s); eps=(int)sqrt(n)/10;
	for(int i=1,a,b,c;i<=x;i++)	scanf("%d %d %d",&a,&b,&c),add(a,b,c),add(b,a,c);
	for(int i=1,a,b,c;i<=y;i++)	scanf("%d %d %d",&a,&b,&c),add(a,b,c);
	spfa();
	for(int i=1;i<=n;i++)
		if(d[i]==inf)	puts("NO PATH");
		else	printf("%d\n",d[i]);
	return 0;
}