#include<bits/stdc++.h>
#define int long long
#define R(x) x=read()
using namespace std;
inline int read() {
	int x=0,y=1;
	char e=getchar();
	while(e<'0'||e>'9') {
		if(e=='-')y=-1;
		e=getchar();
	}
	while(e>='0'&&e<='9') {
		x=(x<<1)+(x<<3)+(e^'0');
		e=getchar();
	}
	return x*y;
}
const int N=25005;
int n,m1,m2,s;
vector<pair<int,int> >G[N];
int cnt,bel[N],ind[N],dis[N];
bool vis[N];

queue<int>Q;
vector<int>vec[N];
void dijkstra(int c) {
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
	for(auto i:vec[c]) {
		q.push({dis[i],i});
	}
	while(!q.empty()) {
		int u=q.top().second;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(auto pii:G[u]) {
			int v=pii.first,w=pii.second;
			if(bel[u]!=bel[v]) {
				if((--ind[bel[v]])==0){
					Q.push(bel[v]);
				}
				if(dis[v]>dis[u]+w) {
					dis[v]=dis[u]+w;
				}
			} else if(dis[v]>dis[u]+w) {
				dis[v]=dis[u]+w;
				q.push({dis[v],v});
			}
		}
	}
}
int fa[N];
int Find(int x) {
	if(x==fa[x])return x;
	else return fa[x]=Find(fa[x]);
}
signed main() {
	R(n),R(m1),R(m2),R(s);
	for(int i=1; i<=n; ++i)fa[i]=i;
	for(int i=1; i<=m1; ++i) {
		int R(u),R(v),R(w);
		G[u].push_back({v,w});
		G[v].push_back({u,w});
		if(fa[Find(u)]!=fa[Find(v)]) {
			fa[Find(u)]=Find(v);
		}
	}
	for(int i=1; i<=n; ++i) {
		if(i==Find(i)) {
			bel[i]=++cnt;
		}
	}
	for(int i=1; i<=n; ++i) {
		bel[i]=bel[Find(i)];
		vec[bel[i]].push_back(i);
	}
	for(int i=1; i<=m2; ++i) {
		int R(u),R(v),R(w);
		G[u].push_back({v,w});
		++ind[bel[v]];
	}
	memset(dis,0x3f,sizeof dis);
	dis[s]=0;
	for(int i=1; i<=cnt; ++i) {
		if(!ind[i]) {
			Q.push(i);
		}
	}
	while(!Q.empty()) {
		int u=Q.front();
		Q.pop();
		dijkstra(u);
	}
	for(int i=1; i<=n; ++i) {
		if(dis[i]>0x3f3f3f3f3f3f) {
			cout<<"Impossible\n";
		} else {
			cout<<dis[i]<<"\n";
		}
	}
	return 0;
}

P3008

直接堆優化spfa+面向樣例程式設計卡過

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#define N 500005
using namespace std;
bool Test_MLE_start;
int _=1,n,m,k,s,tot=0,head[N],dis[N];
bool vis[N];
struct edge{int v,w,nxt;}a[N<<1];
inline int reads(){
	char c=getchar();
	int sum=0,f=1;
	while(!isdigit(c)){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		sum=(sum<<3)+(sum<<1)+(c^'0');
		c=getchar();
	}
	return sum*f;
}
inline void files(){
	freopen("C.in","r",stdin);
	freopen("std.out","w",stdout);
}
inline void clr(){
//	Don't forget!

}
void add(int u,int v,int w){
	a[++tot].v=v;a[tot].w=w;
	a[tot].nxt=head[u];
	head[u]=tot;
}
void bfs(){
	priority_queue<int,vector<int>,greater<int> > q;memset(dis,0x3f,sizeof(dis));q.push(s);dis[s]=0;vis[s]=1;
	while(!q.empty()){
		int x=q.top();q.pop();vis[x]=0;
		for(int i=head[x];i;i=a[i].nxt){
			int y=a[i].v;
			if(dis[y]>dis[x]+a[i].w){
				dis[y]=dis[x]+a[i].w;
				if(!vis[y]) vis[y]=1,q.push(y);
			}
		}
	}
}
bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	_=reads();
	while(_--){
		clr();n=reads(),m=reads(),k=reads(),s=reads();
		for(int i=1;i<=m;i++){
			int u,v,w;u=reads(),v=reads(),w=reads();
			add(u,v,w),add(v,u,w);
		}for(int i=1;i<=k;i++){
			int u,v,w;u=reads(),v=reads(),w=reads();
			add(u,v,w);
		}bfs();for(int i=1;i<=n;i++){
			if(dis[i]==0x3f3f3f3f) puts("Impossible");
			else printf("%d\n",dis[i]);
		}
	}
	return 0;
}